B. 书本检测

内存限制：512 MiB 时间限制：1000 ms 题目类型：交互

转到题库提交记录返回比赛

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

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

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

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

每次测试你可以给出两个数，表示你把区间之间的书拿来测试警报。之后系统会给出一个整数，表示猜测结果，其中表示警报响了，表示警报没响。你可以测试不超过次来求出哪一本书被错拿了。

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

初始输入一个数，表示你的一堆书的总数。

交互输入的方式：

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

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

交互输出：

最多可以测试次，对于每次测试，输出形如 ? 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;
}

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

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