Codeforces Round #703 Guessing the Greatest

题意

这是一道交互式的问题。

存在一个长度为$n$的数组$a$，其中所有的数字都是不同的。

现在你最多可以做20次查询（Easy version可以做40次）。每次查询你需要输出一个区间，然后题目会通过输入给你这个区间中第二大的数的下标。

查询完毕后，你需要输出数组中，最大的数的下标。

我们第一步先查询$[1,n]$，得到整个数组中第二大的下标位置，于是可以得到下图：

我们将区间分为两半，并且查询$2^{nd}$所在的一侧。于是我们大概能得到下图：

如果$1^{st}$在这一侧，则必然返回$2^{nd}$的下标。相反，则必然返回$3^{rd}$的下标。

现在我们继续将可能的区间分为两半，再次查询$2^{nd}$所在的一侧。如果$2^{nd}$在区间范围外，就延申到$2^{nd}$一起查询。具体查询如下图：

于是我们就又把问题的规模缩小了一半。不断重复，我们就能在$log(n)$的次数内把可能的区间长度压缩到1。