31982번 - Koreografija 점수다국어인터랙티브

Jura: I Tvrtko, kakva je jučer bila predstava?

Tvrtko: Bilo je super. Najbolji je dio bio kada se 1000 plesača poredalo redom s lijeva na desno i krenulo izvoditi koreografiju. Svaki od njih je na kostimu imao zapisan broj između $1$ i $1000$, te su svi ti brojevi bili različiti. No moram priznati, kada sam ih promatrao tamo u redu, njihov poredak mi se nije dopao.

Jura: Kako to misliš?

Tvrtko: Promatrao sam neki uzastopni interval plesača u redu te prebrojao koliko postoji parova plesača takvih da je plesač na manjoj poziciji imao veći broj od plesača na većoj poziciji. Sviđa mi se kad je broj takvih parova neparan broj.

Jura: Joj Tvrtko, moraš sagledati cijelu sliku. Budem ja procijenio. Nego, reci mi, kako su išli njihovi brojevi redom?

Tvrtko: Hm... To sam već zaboravio. No mogu ti reći za svaki uzastopni interval plesača je li mi se sviđao ili ne.

Jura: Tako dakle. Ne preostaje nam drugo nego da na temelju toga pokušamo odrediti njihove brojeve.

Ovo je interaktivni zadatak. Vaš program treba uspostaviti dijalog s programom izrađenim od strane organizatora koji odgovara na postavljene upite.

Vaš program može slati upite pisanjem na standardni izlaz. Svaki upit treba biti ispisan u zaseban redak te poprimati oblik “? $a$ $b$”, gdje su $a$ i $b$ prirodni brojevi za koje vrijedi $1 ≤ a ≤ b ≤ 1000$. Brojevi $a$ i $b$ predstavljaju pozicije plesača koje određuju promatrani interval.

Nakon svakog ispisanog upita, vaš program treba napraviti flush izlaza te sa standardnog ulaza pročitati odgovor na upit – broj iz skupa $\{0, 1\}$ koji predstavlja Tvrtkovo mišljenje o navedenom intervalu. Broj $1$ označava da se Tvrtku taj interval sviđao, a $0$ da nije.

Vaš program smije poslati najviše $500\, 000$ ovakvih upita.

Kada je vaš program rekonstruirao brojeve na kostimima plesača, treba na standardni izlaz u zaseban redak ispisati znak ! te zatim ispisati traženi niz brojeva kako se pojavljuju redom s lijeva na desno.

Nakon toga, vaš program ponovno treba napraviti flush izlaza i završiti izvođenje.

Neka je $Q$ najveći broj upita koje je postavio vaš program u svim test primjerima.

Ukoliko je $Q > 500\, 000$, vaš program će osvojiti $0$ bodova.

Inače, broj bodova koji će vaš program ostvariti računa se na temelju sljedeće tablice:

Iako će u zadatku broj plesača uvijek iznositi $1000$, radi ilustracije navodimo primjer interakcije kada bi broj plesača iznosio $4$.

Pretpostavimo da brojevi na kostimima plesača idu redom 2 1 4 3.