Містичний свап#13122

Містичний свап

2 секунди
256 мегабайтів

Це інтерактивна задача.

У перестановці p=(1,2,\ldots,n) поміняли місцями елементи на двох позиціях та (1\le i<j\le n).

За один запит можна вибрати відрізок [l,r] та дізнатися кількість інверсій у p_l,p_{l+1},\ldots,p_r, тобто кількість пар індексів , для яких l\le u<v\le r та p_u>p_v.

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

Вхідні дані

Спочатку інтерактор надсилає ціле число (1\le t\le100) — кількість наборів вхідних даних.

Перед початком кожного набору інтерактор надсилає ціле число (2\le n\le10^4) — довжину перестановки. Значення та приховані.

Вихідні дані

Щоб зробити запит, виведіть окремий рядок ? l r, де 1\le l\le r\le n. У відповідь інтерактор надішле одне ціле число — кількість інверсій на цьому відрізку.

Коли знайдете відповідь, виведіть окремий рядок ! i j, де 1\le i<j\le n. Виведення відповіді не вважається запитом.

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

Після кожної команди виводьте перевід рядка та скидайте буфер виводу: наприклад, cout.flush() у C++ або flush=True у Python.

Некоректна команда, неправильна відповідь або перевищення ліміту запитів призводять до вердикту Wrong Answer. Кожна команда має містити рівно два цілі параметри. Якщо ви отримали або кінець потоку, негайно завершіть програму.

Приклади

Приклад 1

Loading
Loading

Приклад 2

Loading
Loading

Приклад 3

Loading
Loading

Примітка

У прикладах у колонці вхідних даних наведено повідомлення інтерактора, а в колонці вихідних даних — команди програми в порядку їх виконання.

У першому прикладі p=(1,4,3,2,5). Спочатку інтерактор надсилає t=1 та n=5. На запити ? 1 5 і ? 2 4 він відповідає , після чого програма виводить ! 2 4.

У другому прикладі p=(2,1). У третьому прикладі p=(4,2,3,1): на всьому відрізку є інверсій, а на відрізку — .

Оцінювання

  1. Підзадача ( балів): n\le4.

  2. Підзадача ( балів): n\le15.

  3. Підзадача ( балів): i=1.

  4. Підзадача ( балів): без додаткових обмежень.