#1397. 书本检测

这是一道交互题，交互题是指题目的输入会根据你的输出所产生变化。

早晨一女生背着一堆书出了图书馆，结果警报响了。大妈让女生看看是哪本书把警报弄响了，那女生把书倒出来，准备一本一本地测。
大妈见状急了，立刻把书分成两份，第一份过一下，响了。又把这一份分成两份接着测，三回就找到了。
大妈用鄙夷的眼神看着女生，仿佛她不懂算法。

结果图书馆丢了 n - 1 本书。

你背着一堆书出了图书馆，结果警报响了。不过你确实只错拿了一本书，但是你也不知道是哪一本。

每次测试你可以给出两个数 $l,r\ (1 \leq l \leq r \leq n)$，表示你把区间 $\left[ l,r \right]$ 之间的书拿来测试警报。之后系统会给出一个整数 $x\ (x \in \{1,0\})$，表示猜测结果，其中 $1$ 表示警报响了， $0$ 表示警报没响。你可以测试不超过 $80$ 次来求出哪一本书被错拿了。

由于时间宝贵，所以你最多只有 $80$ 次测试机会；

初始输入一个数 $n \ (1 \leq n \leq 10^{18})$，表示你的一堆书的总数。

交互输入的方式：

每当你进行一次测试，就可以从标准输入流中读取一个整数，表示猜测结果，其中 $1$ 表示警报响了，$0$ 表示警报没响。

当你找出错拿的书后，应当立即终止程序，此后不要再继续读入，因为你已经找到了。

交互输出：

最多可以测试 $80$ 次，对于每次测试，输出形如 ? l r 的一行，包含两个 $[1,\ 10^{18}]$ 以内的正整数 $l,r$ 并换行。

当你找出错拿的书后，输出形如 ! x 的一行并换行。其中 x 为错拿的书的编号。

注意：

每次输出之后，必须刷新输出缓冲区，否则将会得到 TLE 的结果。

你只能输出一次表示已经找出错拿书的指令，并且在此之后不应继续输出，因为你已经找到了。

记得输出时要输出换行符。

刷新输出缓冲区的方式如下：

其它语言请参见各自文档。

下面给出 C/C++ 的一种交互方式：

int query(long long l, long long r)
{
	printf("? %lld %lld\n", l, r);
	fflush(stdout);
	int x;
	scanf("%d", &x);
	return x;
}

样例输入

100
0
0
1

样例输出

? 1 1
? 2 2
? 3 3
! 3

对于样例，初始输入表示有 $100$ 本书，你拿第 $1$ 本书去测试，警报没有响，然后再拿第 $2$ 本书去测试，警报还是没有响，拿第 $3$ 本书去测试的时候警报响了，所以确定第三本书是错拿的书。

注意数据范围决定要开的数据类型。