CF1840G2.In Search of Truth (Hard Version)

The only difference between easy and hard versions is the maximum number of queries. In this version, you are allowed to ask at most $1000$ queries.

This is an interactive problem.

You are playing a game. The circle is divided into $n$ sectors, sectors are numbered from $1$ to $n$ in some order. You are in the adjacent room and do not know either the number of sectors or their numbers. There is also an arrow that initially points to some sector. Initially, the host tells you the number of the sector to which the arrow points. After that, you can ask the host to move the arrow $k$ sectors counterclockwise or clockwise at most $1000$ times. And each time you are told the number of the sector to which the arrow points.

Your task is to determine the integer $n$ — the number of sectors in at most $1000$ queries.

It is guaranteed that $1 \le n \le 10^6$.

简单版本与困难版本的唯一区别在于最大查询次数。在本版本中，你最多可以进行 $1000$ 次查询。

这是一道交互式问题。

你正在玩一个游戏。圆被划分为 $n$ 个扇区，扇区按某种顺序编号为 $1$ 到 $n$。你位于相邻的房间中，既不知道扇区总数，也不知道各扇区的编号。此外，还有一支箭，初始时指向某个扇区。初始时，主持人会告诉你箭所指向的扇区编号。此后，你最多可向主持人发出 $1000$ 次指令，每次指令要求将箭逆时针或顺时针移动 $k$ 个扇区。每次移动后，主持人都会告诉你箭当前所指向的扇区编号。

你的任务是在至多 $1000$ 次查询内确定整数 $n$ —— 即圆上扇区的总数。

保证 $1 \le n \le 10^6$。

The input consists of a single integer $x$ ($1 \le x \le n$) — the number of the initial sector.

输入包含一个整数 $x$（$1 \le x \le n$）——初始扇区的编号。

After you determine the integer $n$ — the number of sectors, you should output "! n" ($1 \le n \le 10^6$). After that the program should immediately terminate.

Note that, printing the answer does not count as a query.

It is guaranteed that the integer $n$ and the numbers of the sectors are fixed initially and will not be changed by the jury program depending on the queries.

在确定整数 $n$（扇区数量）后，你需要输出 ! n（其中 $1 \le n \le 10^6$）。之后程序应立即终止。

注意：输出答案不计入查询次数。

保证整数 $n$ 和各扇区的编号在初始时即已固定，且评阅程序不会根据你的查询而更改它们。

Hacks

To hack, use the following test format.

In the first line, output a single integer $n$ ($1 \le n \le 10^6$) — the number of sectors.

In the second line, output $n$ different integers $1 \le a_1, a_2, \dots, a_n \le n$ — the numbers of the sectors in clockwise order, the arrow initially points to the sector with the number $a_1$.

破解

要进行破解，请使用以下测试格式。

第一行输出一个整数 $n$（$1 \le n \le 10^6$）——扇区的数量。

第二行输出 $n$ 个互不相同的整数 $1 \le a_1, a_2, \dots, a_n \le n$ —— 按顺时针顺序排列的扇区编号，箭头初始指向编号为 $a_1$ 的扇区。