Gizemli Takas#13122

Gizemli Takas

2 saniye
256 megabayt

Bu etkileşimli bir problemdir.

p=(1,2,\ldots,n) permütasyonunda ve (1\le i<j\le n) konumlarındaki iki eleman yer değiştirmiştir.

Bir sorguda [l,r] aralığını seçip p_l,p_{l+1},\ldots,p_r dizisindeki inversiyon sayısını, yani l\le u<v\le r ve p_u>p_v koşullarını sağlayan indis çiftlerinin sayısını öğrenebilirsiniz.

Her test durumu için en fazla sorgu kullanarak ve değerlerini bulun. Gizli permütasyon etkileşim başlamadan önce sabitlenir ve değişmez.

Giriş

Önce etkileşimci bir tam sayı (1\le t\le100) — test durumlarının sayısını gönderir.

Her test durumundan önce etkileşimci bir tam sayı (2\le n\le10^4) — permütasyonun uzunluğunu gönderir. ve değerleri gizlidir.

Çıktı

Sorgu yapmak için ayrı bir satırda ? l r yazdırın, burada 1\le l\le r\le n. Etkileşimci tek bir tam sayıyla — bu aralıktaki inversiyon sayısıyla — yanıt verir.

Cevabı bulduğunuzda ayrı bir satırda ! i j yazdırın, burada 1\le i<j\le n. Cevabın yazdırılması sorgu sayılmaz.

Doğru cevaptan sonra, varsa, etkileşimci hemen bir sonraki test durumunun değerini gönderir. Ek bir onay mesajı gönderilmez. Son test durumunu cevapladıktan sonra programınızı sonlandırın.

Her komuttan sonra bir satır sonu yazdırın ve çıkış tamponunu boşaltın: örneğin, C++'ta cout.flush() veya Python'da flush=True kullanın.

Geçersiz bir komut, yanlış bir cevap ya da sorgu limitinin aşılması Wrong Answer sonucunu doğurur. Her komut tam olarak iki tam sayı parametresi içermelidir. alırsanız veya giriş akışının sonuna ulaşırsanız programınızı hemen sonlandırın.

Örnekler

Örnek 1

Loading
Loading

Örnek 2

Loading
Loading

Örnek 3

Loading
Loading

Not

Örneklerde giriş sütununda etkileşimcinin mesajları, çıkış sütununda ise programın komutları çalıştırılma sırasına göre gösterilmiştir.

Birinci örnekte p=(1,4,3,2,5). Etkileşimci önce t=1 ve n=5 gönderir. Hem ? 1 5 hem de ? 2 4 sorgusuna yanıtını verir, ardından program ! 2 4 yazdırır.

İkinci örnekte p=(2,1). Üçüncü örnekte p=(4,2,3,1): tüm aralıkta inversiyon varken aralığında inversiyon vardır.

Puanlama

  1. Alt görev ( puan): n\le4.

  2. Alt görev ( puan): n\le15.

  3. Alt görev ( puan): i=1.

  4. Alt görev ( puan): ek kısıtlama yoktur.