Description: 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$$$. Input Format: The input consists of a single integer $$$x$$$ ($$$1 \le x \le n$$$) — the number of the initial sector. Output Format: 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. Note: 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$$$.