D. More Wrong 交互 思维 逆序对

 题意：

这是一道交互题，它手上有个1到n的排列，但你不知道。

每次询问你可选择lr，它会告诉你lr这个区间上的逆序对的数量，而这次询问的代价就是区间长度的平方。你要通过询问找出最大的数所在的位置，并且你询问的总代价不能超过5*n的平方。

思路：

先把n划分为n/2个长度为2的区间，然后询问出他们中的最大值，然后再对得出的最大值进行反复操作，直到只剩下一个为止。

这个看着简单，细节还是蛮多的。

首先我们如何比较两个数的大小，分两种情况

1，两个数的位置相邻，那么我们直接查询这俩数的区间，逆序对为1，就是前面的数字大。

2，两个数不相邻，那么我们询问两次，第一次是a[i],a[i+1]，第二次是a[i],a[i+1]-1。

不要忘记，当我们开始询问两个数的时候，在以这两个数为端点的区间里，这俩一定就是老大老二，所以第一次和第二次的值如果不同，那么定然是第一次里a[i+1]在为逆序对做出了他的贡献，那就是它比上一个还小。

最后是正确性证明。我们需要计算他的代价。就是n/2为长度为2的区间的数量，乘上2的平方。后面的如法炮制，然后等比数列求和就是2*n的平方，当然每个区间的大数字不是均匀分布的，所以会比我们算的小一点。有些我们需要问两次，而且问的两次区间都会比原本小1，这些索性都不要了，代价直接乘2最大才是4*pow(n,2)。

#include<bits/stdc++.h>
#define de cout<<111<<"\n";
#define fi first
#define se second
#define ll long long
#define kx(a,b) ((a*b)%mod)
#define kplus(a,b) ((a+b)%mod)
#define lowbit(x) x&(-x);
#define up(a,b) ((a-1ll)/b+1ll)
typedef __int128 Int;
using namespace std;
const int N=1000010;
const ll mod=998244353;
//const int mod=1000000007;
typedef pair<int,int> pii;
ll fect[N], infect[N];
ll binpow(ll a,ll b,ll c){
    ll ans=1;
    while(b){
        if(b&1)
            ans=(Int)ans*a%c;
        a=(Int)a*a%c;
        b>>=1;
    }
    return ans;}


int C(int a,int b){
    return fect[a]*infect[b]%mod*infect[a-b]%mod;}


void initzuhe(int n){
    fect[0]=1;infect[0]=1;
    for(int i=1;i<=n;i++){
        fect[i]=(fect[i-1]*i)%mod;
    }
    infect[n-1]=binpow(fect[n-1],mod-2ll,mod);
    for(int i=n-2;i>=1;i--)
        infect[i]=infect[i+1]*(i+1ll)%mod;}


ll test[12]={2,3,5,7,11,13,17,19,23,29,31,37},maxn;
bool check(ll a,ll n){
    ll d=n-1,get=binpow(a,d,n);
    if(get!=1) return 1;
    while((d&1)^1)
        if(d>>=1,(get=binpow(a,d,n))==n-1) return 0;
        else if(get!=1) return 1;
    return 0;
}
bool miller_rabbin(ll n)
{
    if(n<40){
        for(int i=0;i<12;i++) if(test[i]==n) return 1;
        return 0;
    }
    for(int i=0;i<12;i++) if(check(test[i],n)) return 0;
    return 1;
}
ll gcd(ll a,ll b)
{
    return !b?a:gcd(b,a%b);
}
inline ll f(ll x,ll c,ll n)
{
    return ((Int)x*x+c)%n;
}
ll pollard_rho(ll x)
{
    ll s=0,t=0,c=1ll*rand()%(x-1)+1,val=1;
    for(int i=1;;i<<=1,s=t,val=1){
        for(int j=1;j<=i;j++){
            t=f(t,c,x);
            val=(Int)val*abs(t-s)%x;
            if(!(j%127)){
                ll d=gcd(val,x);
                if(d>1) return d;
            }
        }
        ll d=gcd(val,x);
        if(d>1) return d;
    }
}
int a[2010],b[2010];
void solve(){
    int n;cin>>n;
    int idx=0;
    for(int i=0;i<n;i++)a[i]=i+1;
    int m=n;
    int cnt=0ll;
    while(m!=1){
        idx=0;
        if(cnt&1){
            for(int i=1;i<m;i+=2){
                cout<<"? "<<b[i-1]<<" "<<b[i]<<endl;
                        cout.flush();
                int op1;cin>>op1;
                if(b[i-1]+1==b[i]){
                    if(op1==0)a[idx++]=b[i];
                    else a[idx++]=b[i-1];
                }
                else{
                    cout<<"? "<<b[i-1]<<" "<<b[i]-1<<endl;
                            cout.flush();
                    int op2;cin>>op2;
                    if(op1==op2)a[idx++]=b[i];
                    else a[idx++]=b[i-1];
                }
            }
            if(m&1)a[idx++]=b[m-1];
            m=idx;
        }
        else{
            for(int i=1;i<m;i+=2){
                cout<<"? "<<a[i-1]<<" "<<a[i]<<endl;
                        cout.flush();
                int op1;cin>>op1;
                if(a[i-1]+1==a[i]){
                    if(op1==0)b[idx++]=a[i];
                    else b[idx++]=a[i-1];
                }
                else{
                    cout<<"? "<<a[i-1]<<" "<<a[i]-1<<endl;
                        cout.flush();
                    int op2;cin>>op2;
                    if(op1==op2)b[idx++]=a[i];
                    else b[idx++]=a[i-1];
                }

            }
            if(m&1)b[idx++]=a[m-1];
            m=idx;
        }
        cnt++;
    }
    if(cnt&1)cout<<"! "<<b[0]<<endl;
    else cout<<"! "<<a[0]<<endl;
    cout.flush();
}
signed main(){
     std::ios::sync_with_stdio(false);
     std::cin.tie(0);
     std::cout.tie(0);
    //srand((unsigned)time(NULL));
    int t;cin>>t;while(t--)
    solve();
}