Sirli yerdəyişmə#13122

Sirli yerdəyişmə

2 saniyə
256 meqabayt

Bu interaktiv məsələdir.

p=(1,2,\ldots,n) permutasiyasında və mövqelərindəki iki elementin yeri dəyişdirilib (1\le i<j\le n).

Bir sorğuda [l,r] parçasını seçib p_l,p_{l+1},\ldots,p_r altmassivindəki inversiyaların sayını öyrənə bilərsiniz. Bu, l\le u<v\le r və p_u>p_v şərtlərini ödəyən indeks cütlərinin sayıdır.

Hər test halı üçün ən çox sorğu ilə və -ni tapın. Gizli permutasiya qarşılıqlı əlaqə başlamazdan əvvəl müəyyən edilir və dəyişmir.

Giriş

Əvvəlcə interaktor bir tam ədəd (1\le t\le100) — test hallarının sayını göndərir.

Hər test halından əvvəl interaktor bir tam ədəd (2\le n\le10^4) — permutasiyanın uzunluğunu göndərir. və qiymətləri gizlidir.

Çıxış

Sorğu vermək üçün ayrıca sətirdə ? l r çap edin, burada 1\le l\le r\le n. İnteraktor bu parçadakı inversiyaların sayını bir tam ədədlə bildirir.

Cavabı tapdıqda ayrıca sətirdə ! i j çap edin, burada 1\le i<j\le n. Cavabın çap edilməsi sorğu sayılmır.

Düzgün cavabdan sonra növbəti test halı varsa, interaktor dərhal onun qiymətini göndərir. Əlavə təsdiq göndərilmir. Son test halına cavab verdikdən sonra proqramı bitirin.

Hər komandadan sonra yeni sətir çap edin və çıxış buferini boşaldın: məsələn, C++-da cout.flush(), Python-da isə flush=True istifadə edin.

Yanlış komanda, səhv cavab və ya sorğu limitinin aşılması Wrong Answer nəticəsinə səbəb olur. Hər komanda dəqiq iki tam parametrdən ibarət olmalıdır. aldıqda və ya giriş axınının sonuna çatdıqda proqramı dərhal bitirin.

Nümunələr

Nümunə 1

Loading
Loading

Nümunə 2

Loading
Loading

Nümunə 3

Loading
Loading

Qeyd

Nümunələrdə giriş sütununda interaktorun mesajları, çıxış sütununda isə proqramın komandaları icra ardıcıllığı ilə göstərilir.

Birinci nümunədə p=(1,4,3,2,5)-dir. Əvvəlcə interaktor t=1 və n=5 göndərir. ? 1 5 və ? 2 4 sorğularının hər ikisinə cavabını verir, sonra proqram ! 2 4 çap edir.

İkinci nümunədə p=(2,1)-dir. Üçüncü nümunədə p=(4,2,3,1)-dir: bütün parçada , parçasında isə inversiya var.

Bal hesablama

  1. Alt tapşırıq ( bal): n\le4.

  2. Alt tapşırıq ( bal): n\le15.

  3. Alt tapşırıq ( bal): i=1.

  4. Alt tapşırıq ( bal): əlavə məhdudiyyət yoxdur.