Паліндромні масті

Обмеження: 4 сек., 256 МіБ

Це інтерактивна задача (де ваша програма взаємодіє з програмою журі через ввід та вивід).

У Зеника з Марічкою є жеребці різних мастей — гніді, вороні, булані та багато інших. Вони (Зеник, Марічка й коні) хочуть зіграти з вами в гру.

Зеник з Марічкою вишикували $n$ коней у шеренгу. Шеренга задається рядком $s$ довжини $n$ з малих латинських букв. Символи рядка позначають масті коней у порядку шеренги. Наприклад, літера a може позначати гнідого жеребця, b — вороного, c — буланого і т.д.

Коли коней вишикувано, Зеник з Марічкою вже не змінюватимуть їхній порядок у шерензі. Отже, рядок $s$ є зафіксований заздалегідь і не буде змінюватися впродовж гри.

Вам задано число $n$, але ви не бачите шеренгу і не знаєте рядок $s$. Гра полягає в тому, щоб відгадати довжину найбільшого підрядка $s$, що є палідромом.

Рядок $t$ називається підрядком рядка $s$, якщо з рядка $s$ можна видалити якусь (можливо, нульову) кількість символів з початку і якусь (можливо, нульову) кількість символів з кінця, щоб утворився рядок $t$. Наприклад, рядки algo, tester, got, e є підрядками рядка algotester, а рядки lost, alcotester — ні.

Рядок $t$ називається паліндромом, якщо він читається однаково зліва направо та справа наліво. Наприклад, рядки abacaba, pylyp, aa, b є паліндромами, а algotester, oblasna — ні.

Ви можете ставити запитання. Кожне запитання — це пара чисел $l, r$ таких, що $1 \le l \le r \le n$. Зеник і Марічка вам у відповідь скажуть, чи є підрядок $s_l s_{l+1} \dots s_r$ паліндромом.

Щоб гра була цікавішою, Зеник з Марічкою встановили обмеження — ви можете поставити їм не більше ніж $25000$ запитань.

Вхідні дані

Вам задано ціле число $n$ — кількість коней у шерензі.

Після зчитування числа $n$ починається взаємодія між вашою програмою та Зеником з Марічкою, під час якої ваша програма ставить запитання, а Зеник з Марічкою на них відповідають.

Щоб поставити запитання, виведіть «?$\ l \ r$», де $l$, $r$ — цілі числа, що задовольняють $1 \le l \le r \le n$. Це означатиме, що ви хочете дізнатися, чи підрядок $s_l s_{l+1} \dots s_r$ є паліндромом.

У відповідь на запитання Зеник з Марічкою дадуть ціле число $x$ ($x \in \{0, 1\}$), яке ви повинні зчитати у своїй програмі. Якщо $x = 1$, то підрядок є паліндромом; якщо $x = 0$, то ні.

Якщо запитання невалідне (тобто перевищено максимальну кiлькiсть запитань або параметри запитання є невалiдними), Зеник з Марічкою скажуть вам у відповідь -1 та припинять гру. У такому випадку завершiть роботу програми, щоб отримати вердикт Неправильна вiдповiдь. Якщо цього не зробити, ви можете отримати вердикт Помилка часу виконання.

Подбайте про виклик методу flush після виводу кожного рядка. Для цього можна використовувати:

• fflush(stdout), cout << endl або cout.flush() в C++;

• System.out.flush() в Java;

• flush(output) в Pascal;

• sys.stdout.flush() в Python;

• Console.Out.Flush() в C#.

Вихідні дані

Для того, щоб дати відповідь, виведіть рядок у форматі «!$\ p$», де $p$ — довжина найбільшого підрядка $s$, що є палідромом. Після цього ваша програма повинна завершити своє виконання.

Обмеження

$1 \le n \le 7447$.

Оцінювання складається з таких блоків:

• 1 бал за приклад з умови,

• 17 балів: $n \le 100$,

• 36 балів: $n \le 1000$, відповідь на задачу — парне число,

• 21 бал: $n \le 1000$,

• 25 балів: без додаткових обмежень.

Бали за блок ви отримаєте, тільки якщо ваша програма пройде всі тести з блоку.

Примітки

Нижче наведено приклад взаємодії для $n=7$, $s =$cabaaba.