Це інтерактивне завдання. У ньому вам належить реалізувати інтерактивну взаємодію з системою тестування. Це означає, що ви можете робити запити та отримувати відповіді в онлайн-режимі. Зверніть увагу, що введення/виведення у цьому завданні — стандартне (тобто з екрана на екран). Після виведення чергового запиту обов'язково використовуйте функції очищення потоку, щоб частина вашого виводу не залишилася в буфері. Наприклад, на C++ треба використовувати функцію fflush(stdout), Java виклик System.out.flush(), на Pascal flush(output) і stdout.flush() для мови Python.

У цьому завданні вам належить в інтерактивному режимі вгадати число ~x~, яке загадала система тестування. Про задумане число ~x~ відомо, що воно ціле і лежить у межах від ~1~ до ~n~ включно (значення ~n~ відоме заздалегідь).

Ви можете робити запити до системи тестування, кожен запит — це виведення одного цілого числа від ~1~ до ~n~. Є два варіанти відповіді системи тестування на запит:

• рядок "<" (без лапок), якщо задумане число менше від числа із запиту;

• рядок ">=" (без лапок), якщо задумане число більше або дорівнює числу із запиту.

Якщо ваша програма напевно вгадала потрібне число ~x~, виведіть рядок виду "! x", де ~x~ — це відповідь, і завершіть роботу своєї програми.

Вашій програмі дозволяється зробити не більше ~25~ запитів.

Input

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

У першому рядку вхідних даних буде міститися ціле додатне число ~n~ (~1 \le n \le 10^6~) — максимально можливе число, яке може бути загадано.

У наступних рядках на вхід до вашої програми подаватимуться рядки виду "<" і ">=". ~i~-й з цих рядків є відповіддю системи на ваш ~i~-й запит. Після того, як ваша програма вгадала число, виведіть "! x" (без лапок), де ~x~ — це відповідь, і завершіть роботу своєї програми.

Тестуюча система дасть вашій програмі прочитати відповідь на запит із вхідних даних тільки після того, як ваша програма вивела відповідний запит системі та виконала операцію flush.

Output

Для здійснення запитів програма має використовувати стандартний вивід.

Ваша програма повинна виводити запити — цілі числа ~x_i~ (~1 \le x_i \le n~) по одному в рядку (не забувайте виводити переведення рядка після кожного значення ~x_i~). Після виведення кожного рядка програма має виконати операцію flush.

Кожне значення ~x_i~ означає черговий запит до системи. Відповідь на запит програма зможе прочитати із стандартного введення. Якщо ваша програма вгадала число ~x~, виведіть рядок виду "! x" (без лапок), де ~x~ — відповідь, і завершіть роботу програми.

Interaction

Sample Input 1

20

<

>=

>=

Sample Output 1

5

3

4

! 4