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

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

2 seconds
512 megabytes
Hard

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

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

Вам задано два цілі числа та . Сама перестановка вам не відома.

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

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

Input

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

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

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

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

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

Output

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

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

Examples

Example

Loading
Loading

Example 1

Loading
Loading

Note

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

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

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

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

Ввід Вивід Пояснення

7 3

Задані та .

? 1 7 Запитати позицію мінімального елемента на відрізку .

1

Система перевірки відповідає i = 1.

? 4 4 Запитати позицію мінімального елемента на відрізку .

4

Система перевірки відповідає i = 4.

? 2 7 Запитати позицію мінімального елемента на відрізку .

7

Система перевірки відповідає i = 7.

? 2 6 Запитати позицію мінімального елемента на відрізку .

2

Система перевірки відповідає i = 2.

! 2 Вивести k = 2 як відповідь.

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

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

Ввід Вивід Пояснення

4 2

Задані та .

? 1 4 Запитати позицію мінімального елемента на відрізку .

2

Система перевірки відповідає i = 2.

! -1 Вивести -1 як відповідь, оскільки неможливо визначити індекс , для якого p_k = m.