ierarhie

O companie de software are $N$ angajaţi organizaţi ca o ierarhie în care fiecare are cel mult $2$ subalterni direcţi.

Patronul firmei programează de atâta timp, încât pentru el angajaţii nu mai au nume, ci sunt identificaţi prin numere naturale distincte între $1$ şi $N$. Este obligatoriu ca firma să facă o listă cu toţi angajaţii. Din motive greu de înţeles lista se face după următoarele reguli:

• Un angajat fără subalterni va face o listă cu un singur element egal cu numărul lui.
• Un angajat cu un singur subaltern direct va face o listă care începe cu numărul lui şi continuă cu lista creată de subalternul lui direct.
• Un angajat cu doi subalterni direcţi va face o listă care începe cu numărul lui şi continuă cu o interclasare oarecare a listelor create de cei doi subalterni direcţi. O interclasare este o listă care conţine toate elementele listelor care se interclasează; în plus dacă două elemente $a$ şi $b$ se află iniţial în aceeaşi listă, iar $a$ este înaintea lui $b$, atunci după interclasare a se va afla în lista finală înaintea lui $b$.

Lista publicată de companie este cea făcută de patronul firmei (angajatul care este în capul ierarhiei). Voi trebuie să aflaţi structura ierarhică a companiei. Pentru că lista publicată nu este de ajuns, aveţi posibilitatea să întrebaţi pentru doi angajaţi care este primul lor şef comun – cel mai “de jos” (cel mai îndepărtat de patron) angajat care îi are pe amândoi ca subalterni (direcţi sau indirecţi). Aveţi un număr limitat de întrebări pe care puteţi să le efectuaţi.

Interacţiune

Programul vostru nu va citi şi nu va scrie nici un fişier. În schimb, va trebui să implementeze funcția

std::vector<int> solve(int N, std::vector<int> list);

unde list reprezentă lista facută de patron, indexată de la $0$ cu elemente între $1$ și $N$. Programul acum poate pune întrebări pentru a afla primul şef comun a doi angajaţi folosind funcția

int ask(int x, int y);

unde $x$ şi $y$ sunt numere întregi distincte între $1$ şi $N$. Când programul vostru a determinat ierarhia, o va returna ca o listă de $N+1$ elemente, unde al $i$-lea reprezintă şeful direct al angajatului $i$ (primul element este mereu $0$). Dacă $i$ este patronul companiei, șeful va fi egal cu $0$.

Exemplu de interacţiune

Comisia apelează solve(5, {3, 4, 5, 2 ,1}).
Implementarea concurentului apelează ask(2, 4) care returnează 3.
Implementarea concurentului apelează ask(1, 5) care returnează 4.
solve returnează {0, 4, 3, 0, 3, 4}.

Restricții și precizări

• $3 \leq N \leq 4 \ 000$
• Numărul maxim de întrebări pe care le puteţi pune este $40 \ 000$
• dacă programul nu respectă interacţiunea stabilită, va lua $0$ puncte pe testul respectiv
• nu se acordă punctaje parţiale