permut

Nadejda și Zinaida se joacă un joc. În jocul lor, ele consideră o permutare $p_1, \ldots, p_n$, și un șir de numere întregi distincte $a_1, \ldots, a_n$, ambele de lungime $n$. Zinaida cunoaște atât șirul cât și permutarea --- pe când Nadejda nu le cunoaște.

În fiecare rundă a jocului, se întamplă două lucuri:

• Nadejda o poate întreba pe Zinaida care este elementul $a_i$.
• Apoi, Zinaida aplică pemutarea $p$ asupra șirului $a$ --- adică, pentru fiecare $i \in \{ 1, \ldots, n \}$, elementul $a_i$ se mută pe poziția $p_i$.

Cerință

Scopul jocului este ca Nadejda să deducă atât permutarea $p$ cât și șirul inițial $a$, folosind cât mai puține întrebări. O puteți ajuta pe Nadejda să câștige?

Protocol de interacțiune

Această problemă este interactivă! Se citește numărul $n$ prin std::cin. Pentru a-i pune o întrebare Zinaidei, trebuie să afișați pe o linie folosind std::cout:

$\text{\texttt{? i}}$

urmat de un std::endl. După care se citește răspunsul la întrebare folosind std::cin. Dacă acesta este -1, întrebarea a fost invalidă, și trebuie să apelați funcția exit(0) pentru a putea primi verdictul corect (altfel, este posibil să primiți verdictul Execution killed).

După ce ați aflat permutarea și șirul, puteți să-i răspundeți Zinaidei prin a afișa pe o singură linie folosind std::cout:

$\text{\texttt{! p[1] p[2] ... p[n] a[1] a[2] ... a[n]}}$

urmat, desigur, de un std::endl.

Restricții și precizări

• $1 \leq n \leq 2 \; 000$
• $1 \leq a_i \leq 100 \; 000$

*Spre exemplu, $p_3 = 3$ și $p_4 = 4$ sau $p_3 = 4$ și $p_4 = 3$.

Punctare

Pentru un test ce valorează $x$ puncte, dacă soluția voastră efectuează $k$ întrebări, punctajul obținut va fi $x \cdot \text{min}(1.0, e^{-(\frac{k}{n} - 2)})$.

Pentru mai mult de 10$n$ întrebări se va acorda verdictul Too many queries.

De asemenea, în cazul în care ghiciți permutarea sau șirul dar nu pe amândouă, veți primi jumătate din punctajul dat de formula de mai sus (și un verdict corespunzător).

Exemple