Efter att flera hundra år hade gått blev staden JOI en ruinstad. Utforskaren IOI-chan utforskar nu området där biblioteket en gång byggdes. Enligt resultaten av utforskningen är följande känt:

• Det fanns $N$ böcker i bokhyllan på biblioteket i staden JOI. De $N$ böckerna stod placerade i bokhyllan på rad från vänster till höger.
• De $N$ böckerna var numrerade från $1$ till $N$. Men ordningen på böckerna i bokhyllan kunde skilja sig från ordningen på böckernas nummer.
• Med en enda operation var det möjligt att på en gång ta ut sammanhängande placerade böcker ur bokhyllan.

Tyvärr kunde IOI-chan inte hitta några gamla böcker i biblioteket. Men hon hittade en maskin som skötte operationerna för bibliotekets bokhylla. Om vi anger en eller flera böcker genom deras nummer och skickar en fråga till maskinen, svarar den med det minsta antalet operationer som krävs för att ta ut enbart dessa böcker ur bokhyllan.

IOI-chan vill ta reda på ordningen på böckerna i bokhyllan genom att skicka frågor till maskinen. Eftersom svaren från maskinen skulle vara desamma om ordningen på de $N$ böckerna vändes om, behöver hon dock inte ange om böckerna stod placerade från vänster till höger eller från höger till vänster.

Eftersom maskinen är gammal kan hon skicka högst $20\,000$ frågor till maskinen.

Uppgift

Skriv ett program som bestämmer ordningen på böckerna i bokhyllan genom att skicka högst $20\,000$ frågor till maskinen. Det är inte nödvändigt att ange om böckerna var placerade från vänster till höger eller från höger till vänster.

Implementeringsdetaljer

Du ska skicka in en fil.

Namnet på filen är library.cpp. Den ska implementera följande funktion. Programmet ska inkludera library.h.

• void Solve(int N)

  För varje testfall anropas denna funktion en gång.

  • Parametern N är antalet böcker $N$ i bokhyllan.

  Ditt program kan anropa följande funktioner.

  • int Query(const std::vector<int>& M)

    Om en eller flera böcker anges med sina nummer returnerar denna funktion det minsta antalet operationer som krävs för att ta ut enbart dessa böcker ur bokhyllan.

    • Böcker som tas ut ur bokhyllan anges med parametern M, som är en vektor av storlek $N$. För varje $i$ ($1 \le i \le N$) gäller att om M[i-1] = 0 tas bok $i$ inte ut ur bokhyllan. Om M[i-1] = 1 tas bok $i$ ut ur bokhyllan. Om storleken på M skiljer sig från $N$ bedöms ditt program som Wrong Answer [1]. För varje $i$ måste M[i-1] vara lika med antingen 0 eller 1. Det måste finnas minst ett $i$ ($1 \le i \le N$) med M[i-1] = 1. Om minst ett av dessa två villkor inte är uppfyllt bedöms ditt program som Wrong Answer [2]. Om funktionen Query anropas mer än $20\,000$ gånger bedöms ditt program som Wrong Answer [3].

  • void Answer(const std::vector<int>& res)

    Med hjälp av denna funktion svarar ditt program med ordningen på böckerna i bokhyllan. Det är inte nödvändigt att ange om böckerna var placerade från vänster till höger eller från höger till vänster.

    • Parametern res är en vektor av storlek $N$. Den beskriver ordningen på böckerna i bokhyllan. För varje $i$ ($1 \le i \le N$) har den $i$-te boken från vänster i bokhyllan numret res[i-1]. Om storleken på res skiljer sig från $N$ bedöms ditt program som Wrong Answer [4]. res[i-1] måste vara ett heltal mellan $1$ och $N$, inklusive. Om detta villkor inte är uppfyllt bedöms ditt program som Wrong Answer [5]. Dessutom måste heltalen res[0], res[1], $\ldots$, res[N-1] vara parvis olika. Om detta villkor inte är uppfyllt bedöms ditt program som Wrong Answer [6].

  När funktionen Solve avslutas, om antalet anrop till funktionen Answer skiljer sig från $1$, bedöms ditt program som Wrong Answer [7].

  Om ordningen på böckerna som anges av funktionen Solve skiljer sig från ordningen på böckerna i bokhyllan, bedöms ditt program som Wrong Answer [8]. Det är inte nödvändigt att ange om böckerna var placerade från vänster till höger eller från höger till vänster.

Viktiga anmärkningar

• Ditt program får implementera andra funktioner för internt bruk eller använda globala variabler.
• Ditt program får inte använda standardinmatning eller standardutmatning. Ditt program får inte kommunicera med andra filer på något sätt. Däremot får ditt program skriva ut felsökningsinformation till standardfelutmatningen.

Kompilering och testkörning

Du kan ladda ner en arkivfil från tävlingens webbsida som innehåller exempelrättningssystemet (sample grader) för att testa ditt program. Arkivfilen innehåller även en exempelkällkodsfil för ditt program.

Exempelrättningssystemet består av en källkodsfil, som heter grader.cpp. Om ditt program heter library.cpp, placera för att testa dem dessa filer (grader.cpp, library.cpp) och library.h i samma katalog och kör följande kommando för att kompilera dina program.

g++ -std=c++14 -O2 -o grader grader.cpp library.cpp

När kompileringen lyckas skapas den körbara filen grader.

Observera att det faktiska rättningssystemet skiljer sig från exempelrättningssystemet. Exempelrättningssystemet körs som en enda process som läser indata från standardinmatning och skriver resultaten till standardutmatning.

Indata till exempelrättningssystemet

Exempelrättningssystemet läser följande data från standardinmatning.

• Den första raden innehåller heltalet $N$, antalet böcker i bokhyllan.
• Den $i$-te raden ($1 \le i \le N$) av de följande $N$ raderna innehåller heltalet $A_i$. Detta betyder att numret på den $i$-te boken från vänster i bokhyllan är $A_i$.

Utdata från exempelrättningssystemet

När programmet avslutas normalt skriver exempelrättningssystemet följande information till standardutmatning. (Citattecknen skrivs inte ut i verkligheten.)

• Om ditt program bedöms som korrekt skriver exempelrättningssystemet antalet anrop till funktionen Query på formen ”Accepted : 100.”.
• Om ditt program bedöms som Wrong Answer skriver exempelrättningssystemet dess typ på formen ”Wrong Answer [1].”.

Om ditt program uppfyller villkoren för flera typer av Wrong Answer rapporterar exempelrättningssystemet endast en av dem.

Begränsningar

Alla indata uppfyller följande villkor. För betydelsen av $N$ och $A_i$, se ”Indata till exempelrättningssystemet”.

• $1 \le N \le 1\,000$.
• $1 \le A_i \le N$ ($1 \le i \le N$).
• $A_i \ne A_j$ ($1 \le i < j \le N$).

Deluppgifter

Det finns $2$ deluppgifter. Poängen och de ytterligare begränsningarna för varje deluppgift är som följer:

Deluppgift 1 [19 poäng]

• $N \le 200$.

Deluppgift 2 [81 poäng]

Det finns inga ytterligare begränsningar.

Exempel

Här är ett exempel på indata till exempelrättningssystemet och motsvarande funktionsanrop.

Indata 1

5
4
2
5
3
1

Exempelanrop

I denna uppgift är det inte nödvändigt att ange om böckerna var placerade från vänster till höger eller från höger till vänster. Därför bedöms ditt program också som korrekt om det anropar Answer({1,3,5,2,4}) vars parametrar är omvända.