观察题面：\(n\le10^4\)，询问次数 \(\le15\)，因此考虑二分。
用 \(x\) 表示没有被交换过的那个元素。
考虑当询问区间 \([l,r]\) 时，得到的序列满足什么条件，才能确定 \(x\) 在这个区间内。
考虑一个在交换前的序列的 \([l,r]\) 区间内的元素 \(y\)，由题意 \(a_y=y\)。设和 \(y\) 交换的元素为 \(z\)，则 \(z\) 和区间 \([l,r]\) 的关系只有两种情况：
- \(z\notin[l,r]\)。此时这个区间会“进来”一个外面的元素，“出去”一个里面的元素。
- \(z\in[l,r]\)。此时这两个元素还在区间内。
因此，如果一个区间内的元素全部被交换过，则在评测机回答的序列中，值在 \(\bold[l,r]\) 之间的元素个数一定是偶数。
（可以理解为：要么出去，要么成对留下）
那么我们只要查出值在 \([l,r]\) 之间的元素个数，如果为奇，说明 \(x\) 在区间 \([l,r]\) 中；为偶则不在。
二分法缩小询问范围，\(l=r\) 时结束循环。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int N = 1e4 + 5;
int main() {
int t, n;
cin >> t;
while(t--) {
cin >> n;
int l = 1, r = n;
do {
int mid = (l + r) / 2;
cout << "? " << l << ' ' << mid << endl;
int cnt = 0, x;
for(int i = l; i <= mid; ++i) {
cin >> x;
if(x >= l && x <= mid) ++cnt;
}
if(cnt & 1) r = mid;
else l = mid + 1;
} while(r > l);
cout << "! " << l << endl;
}
return 0;
}