Problem H
Carmen Curlers

Carmen 11. Boksen fungerer både som opbevaring og elekrisk varmeapparat.

Den danske opfindelse Carmen Curlers fra 1963 bestod af elektrisk opvarmede papilotter kaldt »curlere« til hårtørring til hjemmebrug i stedet for tørrehjelmen hos frisøren. Produktet blev hurtigt til en verdensomspændende dansk eksportsucces med over $3000$ ansatte i fabrikken i Kalundborg.

Et sæt Carmen Curlers består af $n$ stave nummereret fra $1$ til $n$. Stavene kan have forskellige tykkelser, og hver stav passer på præcis én størrelse curler. For eksempel har det klassiske Carmen 11-sæt tre forskellige stavtykkelser til producentens curlertyper »jumbo«, »stor« og »lille«; stavene $1$, $2$ og $3$ passer til jumbocurlerne, stavene $5$, $10$ og $11$ passer til de små curlere, og de resterende stave passer til de store curlere.

Generelt kan der være mange forskellige sætstørrelser, stavtykkelser og curlertyper. Det kan være svært at se med øjnene, hvilken curler, der passer på hvilken stav, men du kan altid prøve dig frem – enten passer den perfekt, ellers er den klart for lille eller for stor.

Efter en vellykket permanentning vil du gerne samle dit curlersæt igen for at stille det på plads.

Interaktion

Dette er et interaktivt problem, hvor Kattis giver dig svar på, om den $i$’te curler passer på den $j$’te stav.

Begynd med at læse $n$, antallet af stave. Herefter kan du gøre en af to ting:

prøve:

Skriv en linje med et spørgsmålstegn efterfulgt af to heltal mellem $1$ og $n$, altså på formen »? $i$ $j$«. Hermed prøver du at sætte den $i$te curler på den $j$te stav. Kattis svarer da »$-1$«, hvis curleren er for lille; »$0$«, hvis den passer; og »$1$«, hvis den er for stor. Du kan højst spørge $2000$ gange.

svare:

Skriv en linje med et udråbstegn efterfulgt af $n$ heltal mellem $1$ og $n$, altså på formen »! $s_1$ $s_2$ $\cdots $ $s_ n$«. Hermed angiver du stavnumrene, der passer til de $n$ curlere – curler $1$ skal sættes på stav $s_1$, curler $2$ skal sættes på stav $s_2$, osv. Dette afslutter interaktionen og dit program skal ikke skrive mere.

Garantier og delopgaver

Der gælder altid $1\leq n\leq 100$.

Opgaven er opdelt i delopgaver med stærkere garantier, som gør delopgaven nemmere at løse.

Eksempel

I eksempelinteraktionen er $n=3$, og stavtykkelserne er hhv. stor, lille og mellem. Curlerne har størrelser hhv. mellem, stor og lille:

Curler $1$ passer altså på stav $3$, curler $2$ passer på stav $1$, og curler $3$ på stav $2$.

 3

 ? 1 1

 -1

 ? 1 2

 1

 ? 1 3

 0

 ? 2 1

 0

 ! 3 1 2