Запити на мінімум

Обмеження: 2 сек., 512 МіБ

Це інтерактивна задача, у якій ваша програма та система перевірки взаємодіють через стандартні потоки введення та виведення.

Система перевірки має перестановку \(p\) чисел \((1, 2, \dots, n)\).

Вам задано два цілі числа \(n\) та \(m\). Сама перестановка \(p\) вам не відома.

Ви можете поставити системі перевірки не більше ніж \(n - 1\) запитань такого виду.

• Виберіть два цілі числа \(l\) та \(r\) такі, що \(1 \le l \le r \le n\), і запитайте індекс \(i\), для якого \(l \le i \le r\) та \(p_i \le p_j\) для всіх \(l \le j \le r\). Іншими словами, запитайте позицію мінімального елемента на відрізку \(p[l, r]\).

Знайдіть індекс \(k\), для якого \(p_k = m\). Якщо визначити його неможливо, повідомте про це.

Вхідні дані

Спочатку зчитайте зі стандартного потоку введення два цілі числа \(n\) та \(m\).

Після цього ви можете поставити системі перевірки не більше ніж \(n - 1\) запитань, описаних в умові задачі.

Кожне запитання виводьте у стандартний потік виведення у форматі "? \(\ l \ r\)", де \(l\) і \(r\) — цілі числа, що задовольняють умову \(1 \le l \le r \le n\).

У відповідь на це зі стандартного потоку введення буде подано відповідь на ваше запитання — індекс \(i\). При цьому \(l \le i \le r\).

Вихідні дані

Коли ви знайдете індекс \(k\), для якого виконується \(p_k = m\), виведіть його у форматі "!\(\ k\)".

Якщо визначити цей індекс неможливо, виведіть ! -1.

Обмеження

\(1 \le m \le n \le 10^4\).

Примітки

Після кожного повідомлення виводьте символ нового рядка та очищуйте буфер стандартного потоку виведення.

Після виведення відповіді негайно завершіть роботу програми.

Перестановка \(p\) фіксується на початку взаємодії та не змінюється залежно від ваших запитань чи будь-яких інших факторів.

У наведеному нижче прикладі взаємодії \(n = 7\), \(m = 3\), а \(p = (1, 3, 5, 6, 4, 7, 2)\).

Ввід	Вивід	Пояснення
7 3		Задані \(n\) та \(m\).
	? 1 7	Запитати позицію мінімального елемента на відрізку \(p[1, 7]\).
1		Система перевірки відповідає \(i = 1\).
	? 4 4	Запитати позицію мінімального елемента на відрізку \(p[4, 4]\).
4		Система перевірки відповідає \(i = 4\).
	? 2 7	Запитати позицію мінімального елемента на відрізку \(p[2, 7]\).
7		Система перевірки відповідає \(i = 7\).
	? 2 6	Запитати позицію мінімального елемента на відрізку \(p[2, 6]\).
2		Система перевірки відповідає \(i = 2\).
	! 2	Вивести \(k = 2\) як відповідь.

Для \(k = 2\) маємо \(p_k = m\). Отже, якщо програма негайно завершує роботу після цього, тест буде зараховано як правильно розв’язаний.

Нижче наведено ще один приклад для \(n = 4\), \(m = 2\) та \(p = (2, 1, 4, 3)\).

Ввід	Вивід	Пояснення
4 2		Задані \(n\) та \(m\).
	? 1 4	Запитати позицію мінімального елемента на відрізку \(p[1, 4]\).
2		Система перевірки відповідає \(i = 2\).
	! -1	Вивести -1 як відповідь, оскільки неможливо визначити індекс \(k\), для якого \(p_k = m\).