Listan alkio on huippualkio, jos sen vieressä listalla ei ole suurempaa alkiota. Esimerkiksi listalla [2,1,4,3] alkiot 2 ja 4 ovat huippualkioita ja listalla [1,1,1,1] kaikki alkiot ovat huippualkioita.

Lukuja sisältävällä listalla on aina vähintään yksi huippualkio. Tehtäväsi on etsiä jokin listan huippualkio tekemällä rajoitettu määrä kyselyitä listan sisältöön.

Keskustelu

Tämä on interaktiivinen tehtävä, jossa ohjelmasi tulee keskustella arvosteluohjelman kanssa. Keskustelu tapahtuu tulostamalla rivejä ja lukemalla vastauksia.

Sinun tulee lukea ensin kokonaisluku n: listan koko. Listan alkiot on numeroitu 1,2,\dots,n, ja jokainen alkio on kokonaisluku välillä 1 \dots 10^9.

Tämän jälkeen voit suorittaa enintään 50 kyselyä. Jokaisessa kyselyssä tulosta rivi muotoa "? i", missä i on listan indeksi. Kyselyn vastauksena saat listan kohdassa i olevan alkion.

Kun olet löytänyt huippualkion, tulosta rivi muotoa "! i", missä i on listan indeksi. Tämä tarkoittaa, että listan kohdassa i on huippualkio. Tämän rivin tulostamisen jälkeen ohjelmasi tulee päättyä.

Huomaa, että rivin tulostamisen jälkeen saattaa olla tarvetta suorittaa flush-operaatio, jotta tulostettu rivi menee perille arvosteluohjelmalle. Esimerkiksi C++-kielessä rivinvaihto endl tulostusvirrassa saa aikaan flush-operaation.

Kun lähetät ratkaisun palvelimelle, ensimmäisen testin tulos on julkinen, minkä avulla voit varmistaa, että keskustelu toimii oikealla tavalla.

Esimerkki

8
? 4
1
? 5
3
? 6
3
! 5

Tässä tapauksessa n=8 ja listan sisältö on [5,2,4,1,3,3,2,4]. Ohjelma kysyy kohdissa 4, 5 ja 6 olevat luvut ja ilmoittaa sitten, että kohdassa 5 on huippualkio.

Osatehtävä 1 (16 pistettä)

• 1 \le n \le 50

Osatehtävä 2 (42 pistettä)

• 1 \le n \le 100

Osatehtävä 3 (42 pistettä)

• 1 \le n \le 10^6