Dators "ir iedomājies" naturālu skaitli $X$ robežās no $1$ līdz $N$.

Skaitļa $X$ atminēšanai Jūsu programma var veikt vaicājumus. Katrs vaicājums ir formā "Vai iedomātais skaitlis ir $K$?", kur $1 \leq K \leq N$, un uz katru šādu vaicājumu dators dod vienu no trim atbildēm:

• $1$, ja $K < X$,
• $0$, ja $K = X$,
• $-1$, ja $K > X$.

Skaitlis $X$ ir uzminēts tikai tad, ja ir izdarīts vaicājums uz kuru saņemta atbilde $0$.

Katram vaicājumam ir noteikta maksa – ja vaicājumā izmatots skaitlis $K$, tad maksa par šādu vaicājumu ir $K$ eirocenti.

Uzrakstiet datorprogrammu, kas atrod skaitli $X$, iztērējot ne vairāk kā $3400$ eirocentus!

Šis ir interaktīvs uzdevums. Jūsu programmai, sākot darbu, pirmā ievada rinda satur veselu skaitli $N$ $(1 \leq N \leq 500)$. Iedomātā skaitļa vērtību $X$ vērtēšanas sistēma tur slepenībā. Tad jūsu programma var veikt vaicājumus, izvadā rakstot vērtību $K$ $(1 \leq K \leq N)$. Vērtēšanas sistēma izdod atbildi nākamajā ievada rindā. Atbilde ir vesels skaitlis – $-1, 0$ vai $1$, kā aprakstīts iepriekš. Jūsu programma katrā testā var veikt ne vairāk kā $N$ vaicājumus un nedrīkst iztērēt vairāk par $3400$ eirocentiem. Kad uz vaicājumu tiek izdota atbilde $0$, jūsu programmai darbs jābeidz.

Pievērsiet uzmanību, ka, lai gan jau pēc otrā vaicājuma kļuva skaidrs, ka $X$ vērtība ir $4$, nācās veikt vēl trešo vaicājumu, lai saņemtu atbildi $0$. Šajā piemērā aprakstīto vaicājumu kopējās izmaksas bija $3 + 5 + 4 = 12$ eirocenti.