notepad.exe solution codeforces – There are 𝑛n words in a text editor. The 𝑖i-th word has length 𝑙𝑖li (1𝑙𝑖20001≤li≤2000). The array 𝑙l is hidden and only known by the grader.

The text editor displays words in lines, splitting each two words in a line with at least one space. Note that a line does not have to end with a space. Let the height of the text editor refer to the number of lines used. For the given width, the text editor will display words in such a way that the height is minimized.

More formally, suppose that the text editor has width 𝑤w. Let 𝑎a be an array of length 𝑘+1k+1 where 1=𝑎1<𝑎2<<𝑎𝑘+1=𝑛+11=a1<a2<…<ak+1=n+1𝑎a is a valid array if for all 1𝑖𝑘1≤i≤k𝑙𝑎𝑖+1+𝑙𝑎𝑖+1+1++1+𝑙𝑎𝑖+11𝑤lai+1+lai+1+1+…+1+lai+1−1≤w. Then the height of the text editor is the minimum 𝑘k over all valid arrays.

Note that if 𝑤<max(𝑙𝑖)w<max(li), the text editor cannot display all the words properly and will crash, and the height of the text editor will be 00 instead.

You can ask 𝑛+30n+30 queries. In one query, you provide a width 𝑤w. Then, the grader will return the height 𝑤hw of the text editor when its width is 𝑤w.

Find the minimum area of the text editor, which is the minimum value of 𝑤𝑤w⋅hw over all 𝑤w for which 𝑤0hw≠0.

The lengths are fixed in advance. In other words, the interactor is not adaptive.

The first and only line of input contains a single integer 𝑛n (1𝑛20001≤n≤2000)  — the number of words on the text editor.

It is guaranteed that the hidden lengths 𝑙𝑖li satisfy 1𝑙𝑖20001≤li≤2000.

Interaction

Begin the interaction by reading 𝑛n.

To make a query, print “? 𝑤w” (without quotes, 1𝑤1091≤w≤109). Then you should read our response from standard input, that is, 𝑤hw.

If your program has made an invalid query or has run out of tries, the interactor will terminate immediately and your program will get a verdict Wrong answer.

To give the final answer, print “! 𝑎𝑟𝑒𝑎area” (without the quotes). Note that giving this answer is not counted towards the limit of 𝑛+30n+30 queries.

After printing a query do not forget to output end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

• fflush(stdout) or cout.flush() in C++;
• System.out.flush() in Java;
• flush(output) in Pascal;
• stdout.flush() in Python;
• see documentation for other languages.

The first line of input must contain a single integer 𝑛n (1𝑛20001≤n≤2000) — the number of words in the text editor.

The second line of input must contain exactly 𝑛n space-separated integers 𝑙1,𝑙2,,𝑙𝑛l1,l2,…,ln (1𝑙𝑖20001≤li≤2000).

Example
input

Copy
6
? 1

? 9

? 16

! 32

output

Copy
0

4

2



In the first test case, the words are {𝚐𝚕𝚘𝚛𝚢,𝚝𝚘,𝚞𝚔𝚛𝚊𝚒𝚗𝚎,𝚊𝚗𝚍,𝚊𝚗𝚝𝚘𝚗,𝚝𝚛𝚢𝚐𝚞𝚋}{glory,to,ukraine,and,anton,trygub}, so 𝑙={5,2,7,3,5,6}l={5,2,7,3,5,6}.

If 𝑤=1w=1, then the text editor is not able to display all words properly and will crash. The height of the text editor is 1=0h1=0, so the grader will return 00.

If 𝑤=9w=9, then a possible way that the words will be displayed on the text editor is:

• 𝚐𝚕𝚘𝚛𝚢__𝚝𝚘glory__to
• 𝚞𝚔𝚛𝚊𝚒𝚗𝚎__ukraine__
• 𝚊𝚗𝚍_𝚊𝚗𝚝𝚘𝚗and_anton
• __𝚝𝚛𝚢𝚐𝚞𝚋___trygub_

The height of the text editor is 9=4h9=4, so the grader will return 44.

If 𝑤=16w=16, then a possible way that the words will be displayed on the text editor is:

• 𝚐𝚕𝚘𝚛𝚢_𝚝𝚘_𝚞𝚔𝚛𝚊𝚒𝚗𝚎glory_to_ukraine
• 𝚊𝚗𝚍_𝚊𝚗𝚝𝚘𝚗_𝚝𝚛𝚢𝚐𝚞𝚋and_anton_trygub

The height of the text editor is 16=2h16=2, so the grader will return 22.

We have somehow figured out that the minimum area of the text editor is 3232, so we answer it.