寻零

本题选手包（附加文件）为 7z AES-256 加密，解压密码：p68992F82QkHytbzhgNb

题目背景

这是一道交互题。

题目描述

铁四角的档案室里有一排 $n$ 个抽屉，从左到右编号为 $1$ 到 $n$。管理员把 $0,1,\dots,n-1$ 这 $n$ 个数字分别放进了这 $n$ 个抽屉，每个抽屉恰好一个数字，但具体怎么放的，档案室的记录已经遗失了。

你只能向管理员询问：某段连续的抽屉里，没有出现过的最小非负整数是多少。例如，若某段抽屉中放着 $4,2,3,5$，那么这段里没出现过的最小非负整数是 $0$；若放着 $1,0,3$，则是 $2$。

请你找出数字 $0$ 所在的抽屉编号。

为了考察效率，询问次数不能超过 $\lceil\log_2 n\rceil+3$ 次。

实现细节

你需要实现下面的函数：

void solve(int n);

• $n$：抽屉数量，保证 $2 \le n \le 10^{6}$。

你可以调用下面的函数：

int query(int l, int r);

• 返回 $[l,r]$ 这段抽屉中未出现过的最小非负整数。
• 必须保证 $1 \le l \le r \le n$，否则行为未定义。
• 单次运行中调用次数不得超过 $\lceil\log_2 n\rceil+3$ 次。

当你确定答案后，必须调用

void answer(int pos);

报告数字 $0$ 所在的抽屉编号。调用 answer 之后程序应当立即结束。

测试程序方式

本题采用交互方式评测。下发文件中包含 header.h、grader.cpp，编译时请将它们与你的源文件一起编译：

g++ -O2 -std=c++14 -static portal.cpp grader.cpp -o portal

评测时，测试程序会把题目数据通过标准输入传给交互库，再由交互库调用你实现的函数。你不需要写 main 函数，只需要实现 solve。

输入格式

对于编译得到的可执行程序，标准输入格式如下：

• 第一行一个正整数 $n$。
• 第二行 $n$ 个整数，依次表示每个抽屉里的数字。

输出格式

对于编译得到的可执行程序，标准输出格式如下：

• 输出一行一个字符串。1 表示答案正确，0 表示答案错误或询问次数超限。

样例 1 输入

5
4 2 3 0 1

样例 1 输出

1

样例 1 解释

数字 $0$ 放在第 4 个抽屉里。

一种可行的询问方式是：先询问 $[1,3]$，其中放着 $4,2,3$，没出现过的最小非负整数是 $0$；再询问 $[1,2]$，其中放着 $4,2$，返回仍然是 $0$；再询问 $[1,1]$，其中放着 $4$，返回 $0$。三次都返回 $0$，说明 $0$ 不在前三个抽屉里，只能在第 4 或第 5 个。再问 $[4,4]$，其中放着 $0$，返回 $1\ne0$，于是确定是第 4 个抽屉。

样例 2

见选手目录下的 portal/portal2.in 与 portal/portal2.ans。

该样例满足测试点 $1\sim 3$ 的约束条件。

样例 3

见选手目录下的 portal/portal3.in 与 portal/portal3.ans。

该样例满足测试点 $4\sim 6$ 的约束条件。

数据范围

对于所有测试数据，保证 $2\le n\le 10^{6}$，且每个抽屉里放的数恰好构成 $0\sim n-1$ 的一个排列。

特殊性质 A：$0$ 在第一个或最后一个抽屉里。

特殊性质 B：排列是 $0,1,\dots,n-1$。

特殊性质 C：排列是 $n-1,n-2,\dots,0$。

评分方式

每个测试点独立评分：若你的程序在 $\lceil\log_2 n\rceil+3$ 次询问内正确报告 $0$ 的位置，该测试点得满分，否则不得分。