题意：
这是一道交互题，它手上有个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(); }