Zadanie

Inšpektor meškaní: Kde sú vlaky?

Počet bodov: 65

Nitramovi Šullebovi, vedúcemu PR oddelenia nemenovanej železničnej spoločnosti ide o miesto. Práve totiž dovolal s riaditeľom. A ten mu povedal, že ak tento týždeň už konečne nevydá článok, letí!

Nitram však vôbec nevie čo sa deje, týždne ani len nebol v kancelárií. Už začínal byť zúfalý a prezerať pracovné pozície v Lidli, vtom však na to prišiel. Veď použije evergreen vzorec - znižujúce sa meškania vlakov!

No to je síce pekné, ale klesajú vôbec tie meškania? Ktovie, ale to sa jednoducho vyrieši – napíše, že zberná perióda skončila v deň, keď práve klesali (alebo aspoň nerástli). Nemôže si však vybrať akýkoľvek taký deň – keby meškania klesali aj po tomto dni, riaditeľ by videl že vedúci PR si nevie ani len vyfabrikovať najlepšie dáta a to by bol už isto Nitramov koniec.

Nitram vie zistiť priemerné meškanie v akýkoľvek deň jedinou otázkou do databázy. Avšak z kryptických dôvodov má daná tabuľka 1500 stĺpcov¹ a tak jediná query trvá hodiny. Kedy bude Nitram nastupovať za pokladňu?

Úloha

V databáze sa nachádzajú informácie o \(n\) dňoch a priemernom meškaní vlakov počas každého z nich. Databázy sa môžete pýtať na meškanie v ľubovoľný deň, avšak môžete položiť najviac \(k\) takýchto otázok. Nájdite deň, kedy meškanie bolo menšie alebo rovné meškaniam v dňoch pred ním a po ňom. Ak má daný deň iba jedného suseda, tiež môže byť odpoveďou, stačí aby spĺňal nerovnosť s existujúcim susedom.

Vstup a Výstup

Prvý riadok vstupu obsahuje číslo \(n (1 \leq n \leq 10^4)\), ktoré označuje počet dní v databáze. Na druhom riadku sa nachádza číslo \(k\) - maximálny počet otázok, ktoré sa môžete databázy spýtať.

Databáze môžete zadávať otázky vypísaním riadku vo formáte ? x, kde \(x\) je číslo dňa, ktorý vás zaujíma. Ako odpoveď testovač vypíše jeden riadok s jedným prirodzeným číslom do \(10^9\) – meškaním v daný deň. Pozície v poli sú indexované číslami od \(1\) do \(n\).

Na vypísanie odpovede vypíšte riadok formátu ! x, kde \(x\) je pozícia lokálneho nestriktného minima. Ak miním existuje viacej, vypíšte ľubovoľné z nich. Ak žiadne neexistuje, vypíšte ! -1.

Keďže táto úloha je interaktívna, po vypísaní každej otázky je nutné flushovať. V pythone sa to robí parametrom print-u flush : print(..., flush = True), v C++ pomocou cin.flush(). Ak tak neurobíte, váš program môže skončiť verdiktom TLE.

Po vypísaní odpovede odpovede musí váš program skončiť. Taktiež musí skončiť, ak na niektorú otázku dostane odpoveď \(-1\), čo indikuje neplatnú otázku (napríklad nedodržaný formát či prekročený počet otázok). Ak tak neurobí, môžete dostať nesprávny verdikt.

Obmedzenia

Úloha má \(5\) sád vstupov. V jednotlivých sadách platia nasledujúce obmedzenia pre \(k\):

Príklady komunikácie

10000
10000
? 123
234
? 122
234
? 121
572
! 122

Prvok na pozícií 122 je menší alebo rovný obom svojím susedom, je riešením úlohy.

10000
80
? 1
4
? 2
9
! 1

Prvý prvok poľa je menší ako druhý, ktorý je jeho jediným susedom, teda je lokálnym minimom.