Muallif: __thecrash__
H. Sirli vodiy
Vaqt limiti: 2000 ms Xotira limiti: 256 mb
Marsga yuborilgan "Roverchik" nomli tadqiqot roboti uzun tog' tizmasi bo'ylab harakatlanmoqda. Tizma \(N\) ta nuqtadan iborat (\(1\) dan \(N\) gacha raqamlangan), har bir nuqtaning o'z balandligi bor va barcha balandliklar bir-biridan farq qiladi.
Yer nazorat markazi Roverchikka topshiriq berdi: tizmada "vodiy nuqtasi"ni toping — ya'ni shunday nuqtaki, uning balandligi ikkala qo'shnisining balandligidan past bo'lsin (agar nuqta chekkada bo'lsa, yo'q qo'shni cheksiz baland tog' deb hisoblanadi). Bunday nuqta tizmada albatta topiladi.
Muammo shundaki, Roverchikning balandlik o'lchagichi juda ko'p energiya sarflaydi — shuning uchun siz ko'pi bilan \(130\) marta o'lchov qilishingiz mumkin. Ortiqcha o'lchov qilsangiz, missiya muvaffaqiyatsiz deb topiladi.
Yer nazorat markazi bilan aloqa quyidagicha ishlaydi:
- Siz "\(? \,\, i\)" deb yuborsangiz (\(1 \le i \le N\)), markaz sizga \(i\)-nuqtaning balandligini qaytaradi.
- Javobni topgach, "\(! \,\, i\)" deb yuborasiz — bu sizning yakuniy javobingiz (\(i\) — vodiy nuqtasi indeksi). Shundan so'ng dasturingiz darhol ishini tugatishi kerak.
Roverchikka yordam bering!
Kiruvchi ma'lumotlar
Birinchi qatorda \(N\) butun soni beriladi — bu tog' tizimidagi nuqtalar soni (\(1 \le N \le 10^{18}\)).
Har bir so'rov "\(? \,\, i\)" ko'rinishida yuboriladi (\(1 \le i \le N \le 10^{18}\)) va flush qilinadi. Javobida \(i\)-nuqtaning balandligi qaytadi (barcha balandliklar [\(-10^{18}, 10^{18}\)], bir-biridan farqli).
Yakuniy javob "\(! \,\, i\)" ko'rinishida chiqariladi, shundan so'ng dastur darhol tugaydi. Ruxsat etilgan so'rovlar soni — ko'pi bilan \(130\) ta ("\(i\)" bunga kirmaydi).
Chiquvchi ma'lumotlar
Dasturingiz alohida "javob fayli" chiqarmaydi — u faqat "\(?\)" so'rovlarini yuboradi va oxirida "\(! \,\, i\)" bilan yakuniy javobini beradi.
Misollar
| # | Input.txt | Output.txt |
|---|---|---|
1 |
9 8 2 9 |
? 3 ? 4 ? 5 ! 4 |
2 |
9 7 3 1 2 |
? 2 ? 4 ? 5 ? 6 ! 5 |
Izoh
ESLATMA: Bu — interaktiv masala. Sizning har bir so'rovingiz hakamlar tizimiga darhol yetib borishi uchun, har safar chiqargan qatoringizdan so'ng bufer tozalanishi (flush qilinishi) SHART:
- C/C++: fflush(stdout);
- Python: sys.stdout.flush();
Buni bajarmasangiz, dasturingiz to'g'ri fikrlagan bo'lsa ham, javob hakamlarga yetib bormay, Time Limit xatosi bilan yakunlanadi.