Единственное отличие между версиями — максимальное количество запросов. В этой версии вы можете сделать не более \(1000\) запросов.
Это интерактивная задача.
Вы играете в игру. Круг разделен на \(n\) секторов, секторы пронумерованы от \(1\) до \(n\) в некотором порядке. Вы находитесь в соседней комнате и не знаете ни количество секторов, ни порядка их нумерации. Также есть стрелка, которая изначально указывает на какой-то сектор. Изначально ведущий сообщает вам номер сектора, на который указывает стрелка. После этого вы можете попросить ведущего переместить стрелку на \(k\) секторов по часовой стрелке или против часовой стрелки не более чем \(1000\) раз. И каждый раз вам сообщается номер сектора, на который указывает стрелка.
Ваша задача определить число \(n\) — количество секторов, используя не более чем \(1000\) запросов.
Гарантируется, что \(1 \le n \le 10^6\).
Выходные данные
После того, как вы определите число \(n\) — количество секторов, выведите «! n» (\(1 \le n \le 10^6\)). После этого программа должна немедленно завершиться.
Обратите внимание, что вывод ответа не считается запросом.
Гарантируется, что число \(n\) и номера секторов зафиксированы изначально и не будут меняться программой жюри в зависимости от запросов.
Протокол взаимодействия
После описания ввода вы можете задавать запросы. Запросы могут быть двух типов:
- «+ k» (\(0 \le k \le 10^9\)) — попросить переместить стрелку на \(k\) секторов по часовой стрелке.
- «- k» (\(0 \le k \le 10^9\)) — попросить переместить стрелку на \(k\) секторов против часовой стрелки.
После каждого запроса вы должны считать целое число \(x\) (\(1 \le x \le n\)) — номер текущего сектора, на который указывает стрелка.
Всего вы можете сделать не более \(1000\) запросов.
Если вы сделаете слишком много запросов, вы получите вердикт Wrong answer.
После вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:
- fflush(stdout) или cout.flush() в C++;
- System.out.flush() в Java;
- flush(output) в Pascal;
- stdout.flush() в Python;
- смотрите документацию для других языков.
Примечание
Взломы
Для взломов используйте следующий формат теста.
В первой строке выведите одно целое число \(n\) (\(1 \le n \le 10^6\)) — количество секторов.
Во второй строке выведите \(n\) различных целых чисел \(1 \le a_1, a_2, \dots, a_n \le n\) — номера секторов по часовой стрелке, стрелка изначально указывает на сектор с номером \(a_1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1
5
6
7
2
10
9
8
4
3
1
|
+ 1
+ 1
+ 1
+ 1
+ 1
+ 1
+ 1
+ 1
+ 1
+ 1
! 10
|