E. блокнот.exe
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это интерактивная задача.

В текстовом редакторе есть $$$n$$$ слов. Длина $$$i$$$-го слова составляет $$$l_i$$$ ($$$1 \leq l_i \leq 2000$$$). Массив $$$l$$$ скрыт и известен только интерактору.

Текстовый редактор отображает слова в строках, разделяя каждые два слова в строке хотя бы одним пробелом. Обратите внимание, что строка не обязательно должна заканчиваться пробелом. Будем называть высотой текстового редактора количество использованных строк. При данной ширине текстовый редактор будет отображать слова таким образом, чтобы высота была минимальной.

Более формально, предположим, что текстовый редактор имеет ширину $$$w$$$. Пусть $$$a$$$  — массив длины $$$k+1$$$, где $$$1=a_1 < a_2 < \ldots < a_{k+1}=n+1$$$. $$$a$$$ является допустимым массивом, если для всех $$$1 \leq i \leq k$$$, $$$l_{a_i}+1+l_{a_i+1}+1+\ldots+1+l_{a_{i+1}-1} \leq w$$$. Тогда высота текстового редактора является минимальным $$$k$$$ по всем допустимым массивам.

Обратите внимание, что если $$$w < \max(l_i)$$$, то текстовый редактор не сможет правильно отобразить все слова и завершится аварийно, а высота текстового редактора будет равна $$$0$$$.

Вы можете задать $$$n+30$$$ запросов. В одном запросе вы указываете ширину $$$w$$$. В ответ интерактор вернет высоту $$$h_w$$$ текстового редактора, если его ширина равна $$$w$$$.

Найдите минимальную площадь текстового редактора, которая является минимальным значением $$$w \cdot h_w$$$ по всем $$$w$$$, для которых $$$h_w \neq 0$$$.

Длины зафиксированы заранее. Другими словами, интерактор не является адаптивным.

Входные данные

Первая и единственная строка ввода содержит единственное целое число $$$n$$$ ($$$1 \leq n \leq 2000$$$)  — количество слов в текстовом редакторе.

Гарантируется, что скрытые длины $$$l_i$$$ удовлетворяют $$$1 \leq l_i \leq 2000$$$.

Протокол взаимодействия

Начните взаимодействие с чтения $$$n$$$.

Чтобы сделать запрос, выведите «? $$$w$$$» (без кавычек, $$$1 \leq w \leq 10^9$$$). Затем вы должны прочитать ответ из стандартного ввода, то есть высоту $$$h_w$$$.

Если ваша программа сделала некорректный запрос или исчерпала количество попыток, интерактор немедленно завершит работу программы, а ваша программа получит вердикт Неправильный ответ.

Чтобы дать окончательный ответ, выведите «! $$$area$$$» (без кавычек). Обратите внимание, что этот ответ не учитывается в лимит $$$n+30$$$ запросов.

После вывода каждого запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:

  • fflush(stdout) или cout.flush() в C++;
  • System.out.flush() в Java;
  • flush(output) в Pascal;
  • stdout.flush() в Python;
  • смотрите документацию для других языков.

    Взломы

    Первая строка ввода должна содержать одно целое число $$$n$$$ ($$$1 \leq n \leq 2000$$$) — количество слов в текстовом редакторе.

    Вторая строка ввода должна содержать ровно $$$n$$$ разделенных пробелами целых чисел $$$l_1,l_2,\ldots,l_n$$$ ($$$1 \leq l_i \leq 2000$$$).

Пример
Входные данные
6

0

4

2

Выходные данные

? 1

? 9

? 16

! 32
Примечание

В первом примере слова  — $$$\{\texttt{glory},\texttt{to},\texttt{ukraine},\texttt{and},\texttt{anton},\texttt{trygub}\}$$$, поэтому $$$l=\{5,2,7,3,5,6\}$$$.

Если $$$w=1$$$, то текстовый редактор не сможет правильно отобразить все слова и завершится аварийно. Высота текстового редактора равна $$$h_1=0$$$, поэтому интерактор вернет $$$0$$$.

Если $$$w=9$$$, то возможный способ отображения слов в текстовом редакторе следующий:

  • $$$\texttt{glory__to}$$$
  • $$$\texttt{ukraine__}$$$
  • $$$\texttt{and_anton}$$$
  • $$$\texttt{__trygub_}$$$

Высота текстового редактора равна $$$h_{9}=4$$$, поэтому интерактор вернет $$$4$$$.

Если $$$w=16$$$, то возможный способ отображения слов в текстовом редакторе следующий:

  • $$$\texttt{glory_to_ukraine}$$$
  • $$$\texttt{and_anton_trygub}$$$

Высота текстового редактора равна $$$h_{16}=2$$$, поэтому интерактор вернет $$$2$$$.

Мы каким-то образом выяснили, что минимальная площадь текстового редактора равна $$$32$$$, поэтому отвечаем её.