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

В текстовом редакторе есть $$$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$$$.

Чтобы сделать запрос, выведите «? $$$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$$$).