To jest zadanie interaktywne.

Sędzia ukrywa permutację $p$ długości $n=30000$. Twoim zadaniem jest znaleźć indeks minimalnej wartości tej permutacji.

Sędzia jest nieadaptacyjny: permutacja jest wybierana przed rozpoczęciem interakcji i nigdy się nie zmienia.

W przeciwieństwie do zwykłych zapytań porównawczych, sędzia porównuje tylko bieżące zapytanie z poprzednim. Dokładniej, jeśli twoim poprzednim zapytanym indeksem był $i$, a teraz zapytasz o indeks $j$, sędzia informuje cię o wyniku porównania $p_i$ i $p_j$.

Możesz wykonać co najwyżej $q_{\max}=42000$ zapytań.

Oficjalne dane oceniające składają się z 100 oddzielnych plików testowych. Twój program jest uruchamiany niezależnie na każdym pliku.

Interakcja

Na początku interakcji twój program musi wczytać dwie liczby całkowite

$$ n \quad q_{\max}. $$

W oficjalnych testach $n=30000$ i $q_{\max}=42000$.

Aby zadać zapytanie, wypisz jeden wiersz w następującym formacie:

$$ \text{? j} $$

gdzie $1 \le j \le n$.

Sędzia odpowiada jednym znakiem:

• < jeśli $p_i < p_j$, gdzie $i$ oznacza poprzednie zapytanie (jeśli istnieje);
• = jeśli jest to pierwsze zapytanie lub $p_i = p_j$;
• > jeśli $p_i > p_j$, gdzie $i$ oznacza poprzednie zapytanie (jeśli istnieje).

Ponieważ $p$ jest permutacją, odpowiedź = po pierwszym zapytaniu może wystąpić tylko wtedy, gdy zapytasz o ten sam indeks co w poprzednim zapytaniu. Jeśli sędzia odpowie -1, twój program musi natychmiast się zakończyć. Oznacza to, że twój program naruszył protokół interakcji i otrzyma Błędną odpowiedź.

Aby podać ostateczną odpowiedź, wypisz jeden wiersz w następującym formacie:

$$ \text{! a} $$

gdzie $a$ to indeks, który według ciebie zawiera wartość minimalną. Po wypisaniu odpowiedzi program musi się zakończyć. Ostateczna odpowiedź nie jest liczona jako zapytanie.

Jeśli twój program wykona więcej niż $q_{\max}$ zapytań, zapyta o nieprawidłowy indeks, wypisze nieprawidłowe polecenie lub poda błędną ostateczną odpowiedź, otrzyma Błędną odpowiedź.

Po każdym wypisanym zapytaniu lub odpowiedzi opróżnij bufor wyjścia. Na przykład w C++ możesz użyć endl lub cout.flush().

Uwagi

Ten przykład to tylko przykładowa interakcja i nie pojawi się w rzeczywistych danych testowych. Wiersze postaci (receiving ... output) to symbole zastępcze użyte tylko dla wyrównania zapytań i odpowiedzi sędziego w przykładzie. W prawdziwym teście ława przysięgłych nie wypisze tych wierszy zastępczych, a uczestnik nie powinien ich czytać ani wypisywać.

W tej przykładowej interakcji ukryta permutacja to $p=(3,1,4,2)$. Punkty poniżej opisują interakcję pokazaną w przykładzie.

• Sędzia najpierw wysyła $n=4$ i limit zapytań $5$.
• Pierwsze zapytanie ? 1 otrzymuje =, ponieważ nie ma poprzedniego zapytanego indeksu.
• Zapytanie ? 2 porównuje $p_1=3$ z $p_2=1$, więc sędzia odpowiada >.
• Zapytanie ? 4 porównuje $p_2=1$ z $p_4=2$, więc sędzia odpowiada <. Minimum znajduje się na indeksie $2$, więc ! 2 jest poprawne.

Narzędzie do lokalnej interakcji: Załączony attachments/local_interactive.py może odtworzyć to lokalne ustawienie z parametrem --perm 3,1,4,2 --limit 5, ale przejście tego testu nie gwarantuje przejścia oficjalnych danych oceniających.