Þetta er gagnvirkt verkefni.
VegiCat þekkir fylki $a_1, a_2, \ldots, a_n$, þar sem hvert stak er $0$, $1$ eða $2$. Hann vill ekki segja þér gildin í því, en þú getur spurt hann spurninga. Í hverri fyrirspurn velur þú tvo vísa $i$ og $j$, og VegiCat segir þér hvort $a_i > a_j$.
VegiCat biður þig um að prenta vísana í ekki-minnkandi röð eftir samsvarandi gildum í fylkinu. Það er, finndu umröðun $p_1, p_2, \ldots, p_n$ á $1, 2, \ldots, n$ þannig að
$$a_{p_1} \le a_{p_2} \le \cdots \le a_{p_n}.$$
Þú mátt gera að hámarki $2n - 3$ fyrirspurnir í hverju prófunartilfelli.
Gagnvirki prófarinn er aðlögunarhæfur (adaptive). Þetta þýðir að fylkið er ekki ákveðið fyrir fram. Prófarinn tryggir að alltaf sé til að minnsta kosti eitt fylki með stökum úr $\{0, 1, 2\}$ sem samræmist öllum svörum sem gefin hafa verið hingað til. Lokaumröðunin þín verður að vera gild fyrir hvert einasta fylki sem samræmist öllum svörum.
Inntak
Fyrsta línan inniheldur heiltölu $T$ ($1 \le T \le 250$), fjölda prófunartilfella. Lýsing á prófunartilfellunum fylgir.
Hvert prófunartilfelli byrjar á heiltölu $n$ ($2 \le n \le 500$), lengd fylkisins.
Summa $n$ yfir öll prófunartilfelli fer ekki yfir $500$.
Samskipti
Til að gera fyrirspurn skaltu prenta línu á eftirfarandi sniði:
? i j
Hér er $1 \le i, j \le n$. Eftir hverja fyrirspurn skaltu lesa eina heiltölu:
- $1$, ef $a_i > a_j$;
- $0$, ef $a_i \le a_j$.
Fyrirspurnir með $i = j$ og endurteknar fyrirspurnir eru leyfðar og teljast með í fjölda fyrirspurna.
Þegar þú hefur ákvarðað röðina skaltu prenta línu á eftirfarandi sniði:
! p_1 p_2 ... p_n
Hver vísir frá $1$ til $n$ verður að koma fyrir nákvæmlega einu sinni. Að prenta svarið telst ekki sem fyrirspurn.
Ef svarið þitt er rétt skaltu halda áfram í næsta prófunartilfelli með því að lesa $n$ þess, eða ljúka keyrslu forritsins ef þetta var síðasta prófunartilfellið. Prófarinn sendir ekki sérstaka staðfestingu á eftir svari.
Eftir að hver fyrirspurn eða svar er prentað skaltu prenta nýja línu og tæma úttaksbiðminnið (flush). Til að tæma úttaksbiðminnið geturðu notað:
fflush(stdout)eðacout.flush()í C/C++;System.out.flush()í Java og Kotlin;sys.stdout.flush()í Python.
Ef þú gerir ógilda fyrirspurn, ferð yfir hámarksfjölda fyrirspurna eða prentar rangt svar færðu dóminn Wrong Answer. Úttak sem fylgir ekki tilgreindu sniði fær einnig dóminn Wrong Answer. Í þessum tilvikum hættir prófarinn keyrslu án þess að senda villuboð.
Examples
Input 1
2 3 1 1 2 0
Output 1
? 1 2 ? 2 3 ! 3 2 1 ? 1 2 ! 1 2
Note
Í fyrsta prófunartilfellinu skila fyrirspurnirnar ? 1 2 og ? 2 3 báðar $1$, þannig að $a_1 > a_2 > a_3$. Því er $(3, 2, 1)$ rétt svar.
Í öðru prófunartilfellinu skilar fyrirspurnin ? 1 2 gildinu $0$, þannig að $a_1 \le a_2$. Því er $(1, 2)$ rétt svar.