Problem C
Where's Waldo?

Det finns en gömd permutation $P_{1},P_{2},\ldots ,P_{N}$ av längd $N$, som är garanterad att vara genererad uniformt slumpmässigt. Permutationen innehåller talen $1, 2, 3, \ldots , N$ exakt en gång vardera i någon okänd ordning.

Du kan välja positioner $l$ och $r$, och ställa frågor på formen: “Vad är summan av $P_ l + P_{l+1} + \cdots + P_ r$?”

Din uppgift är att hitta på vilken position $1$:an befinner sig i $P$ med så få frågor som möjligt. Du får poäng beroende på hur få frågor du ställer.

Interaktion

Ditt program ska först läsa in två heltal på en rad, $T$ och $N$. $T$ är antalet omgångar ditt program kommer köras, och $N$ är längden på $P$.

Därefter sker $T$ omgångar:

När en omgång börjar kan du börja ställa frågor. Skriv ut en rad med “? a b” för att fråga efter summan av talen mellan position $a$ och $b$ ($1 \leq a \leq b \leq N$).

Efter varje fråga ska ditt program läsa in ett heltal, summan av talen i intervallet.

När du har hittat vilken position $1$:an befinner sig på, skriv ut en rad på formen “! i”, där $i$ är det index sådant att $P_ i = 1$. Efter att du skrivit ut detta börjar nästa omgång.

Se till att flusha outputen efter varje query, annars kan du få Time Limit Exceeded. I C++ kan detta göras med exempelvis cout << flush eller fflush(stdout); i Python med stdout.flush(); och i Java med System.out.flush().

Poängsättning

Ditt program kommer att testas mot ett enda testfall, med $N = T = 1000$.

Om någon omgång ger fel svar kommer inskickningen bedömas som Wrong Answer.

Låt $M$ vara antalet frågor ditt program ställer över alla $T$ omgångar. Du kommer då få $\min (100, 220 - \frac{M}{2500})$ poäng. Om du får negativ poäng så räknas det som noll poäng.

Alltså, om du använder fler än $550\, 000$ frågor får du 0 poäng, och om du använder $300\, 000$ eller färre frågor får du 100 poäng. Där emellan växer poängen linjärt.

 2 10

 ? 1 10

 55

 ? 1 5

 40

 ? 6 6

 1

 ! 6
 ? 1 1

 1

 ! 1