简单版本和困难版本之间的唯一区别是最大查询数。在此版本中,您最多可以提出 $$$1000$$$ 查询。
这是一个交互问题。
您正在玩游戏。该圆被分为 $$$n$$$ 个扇区,扇区按某种顺序从 $$$1$$$ 到 $$$n$$$ 编号。您在相邻的房间,不知道扇区的数量或扇区的编号。还有一个最初指向某个扇区的箭头。最初,主机告诉您箭头指向的扇区号。之后,您可以要求主持人将箭头$$$k$$$扇区逆时针或顺时针移动最多$$$1000$$$次。每次都会告诉您箭头指向的扇区的编号。
您的任务是确定整数 $$$n$$$ — 最多 $$$1000$$$ 查询中的扇区数。
保证$$$1 \le n \le 10^6$$$。
输入
输入由单个整数 $$$x$$$ ($$$1 \le x \le n$$$) 组成 - 初始扇区的编号。
互动
阅读输入说明后,您可能会提出疑问。查询可以有两种类型:
1. "+ k" ($$$0 \le k \le 10^9$$$) — 要求顺时针移动箭头 $$$k$$$ 扇区。
2. "- k" ($$$0 \le k \le 10^9$$$) — 要求逆时针移动箭头 $$$k$$$ 扇区。
每次查询后,您应该读取一个整数 $$$x$$$ ($$$1 \le x \le n$$$) — 箭头指向的当前扇区的编号。
您总共最多可以进行 $$$1000$$$ 查询。
如果您询问太多,您将得到错误的答案。
打印查询或答案后,不要忘记输出行尾并刷新输出。否则,您将超出空闲限制。为此,请使用:
- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。
输出
确定整数 $$$n$$$ — 扇区数后,应输出“! n” ($$$1 \le n \le 10^6$$$)。之后程序应立即终止。
请注意,打印答案不算作查询。
保证整数$$$n$$$和扇区的数量最初是固定的,并且陪审团程序不会根据查询而改变。
示例
输入 #1
1 5 6 7 2 10 9 8 4 3 1
输出 #1
+ 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 ! 10
注意
黑客
要破解,请使用以下测试格式。
在第一行中,输出单个整数 $$$n$$$ ($$$1 \le n \le 10^6$$$) — 扇区数。
第二行,输出$$$n$$$不同的整数$$$1 \le a_1, a_2, \dots, a_n \le n$$$——按顺时针顺序排列的扇区编号,箭头初始指向编号为$$$a_1$$$的扇区。