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

• Det fanns $N$ böcker i bokhyllan på biblioteket i JOI-staden. De $N$ böckerna var 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 ta sammanhängande placerade böcker från bokhyllan på en gång.

Tyvärr kunde IOI-chan inte hitta några gamla böcker i biblioteket. Men hon hittade en maskin som hanterade 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 minimala antalet operationer som krävs för att ta endast dessa böcker från bokhyllan.

IOI-chan vill veta ordningen på böckerna i bokhyllan genom att skicka frågor till maskinen. Men eftersom svaren från maskinen skulle bli desamma om ordningen på de $N$ böckerna vändes om, behöver hon inte ange om böckerna var 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 anger 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 genom sina nummer returnerar denna funktion det minimala antalet operationer som krävs för att ta endast dessa böcker från bokhyllan.

    • Böcker som tas från bokhyllan anges av parametern M, som är en vektor av storlek $N$. För varje $i$ ($1 \le i \le N$), om M[i-1] = 0, tas boken $i$ inte från bokhyllan. Om M[i-1] = 1, tas boken $i$ från bokhyllan. Om storleken på M skiljer sig från $N$ bedöms ditt program som Wrong Answer [1]. För varje $i$ ska 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] ska vara ett heltal mellan $1$ och $N$, inklusive. Om detta villkor inte är uppfyllt bedöms ditt program som Wrong Answer [5]. Dessutom ska heltalen res[0], res[1], …, res[N-1] vara olika varandra. 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 meddelanden

• Ditt program kan implementera andra funktioner för internt bruk, eller använda globala variabler.
• Ditt program får inte använda standard inmatning och standard utmatning. Ditt program får inte kommunicera med andra filer på något sätt. Ditt program får dock skriva ut felsökningsinformation till standard error.

Kompilering och provkörning

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

Exempelrättaren består av en källfil, som är grader.cpp. Om ditt program är library.cpp, för att testa dem, lägger du 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 genereras den körbara filen grader.

Observera att den faktiska rättaren skiljer sig från exempelrättaren. Exempelrättaren kommer att köras som en enda process, som läser indata från standard inmatning och skriver resultaten till standard utmatning.

Indata för exempelrättaren

Exempelrättaren läser följande data från standard inmatning.

• 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ättaren

När programmet avslutas framgångsrikt skriver exempelrättaren följande information till standard utmatning. (Citattecknen skrivs inte ut i verkligheten.)

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

Om ditt program bedöms som flera typer av Wrong Answer rapporterar exempelrättaren endast en av dem.

Begränsningar

All indata uppfyller följande villkor. För betydelsen av $N$ och $A_i$, se Indata för exempelrättaren.

• $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 följande:

Deluppgift 1 [19 poäng]

• $N \le 200$.

Deluppgift 2 [81 poäng]

Det finns inga ytterligare begränsningar.

Exempelkommunikation

Här är ett exempel på indata för exempelrättaren 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 som korrekt även om det anropar Answer( { 1,3,5,2,4 } ) vars parametrar är omvända.