直接求最大值不好求。我们可以采用一个交互常见的套路，维护可能的答案集合 \(S\)，每次剔除掉一些。
考虑初始把 \(a_{i - 1} < a_i > a_{i + 1}\) 的 \(i\) 加入 \(S\)，每次取出 \(S\) 中差最小的一对元素 \(i, j\)，那么若 \(a_i > a_j\)，\(a_i\) 就大于 \([i + 1, j]\) 的所有元素，也就是 \([i, j]\) 与 \([i + 1, j]\) 的逆序对之差为 \(j - i\)，此时我们删除 \(j\)，否则删除 \(i\)。
使用的金币数不超过 \(n + \sum\limits_{i = 1}^n (\frac{n}{i})^2 < 2n^2 + n\)，可以通过。
code
// Problem: D. More Wrong
// Contest: Codeforces - Codeforces Round 890 (Div. 2) supported by Constructor Institute
// URL: https://codeforces.com/contest/1856/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 2020;
int n, a[maxn];
inline int ask(int l, int r) {
printf("? %d %d\n", l, r);
fflush(stdout);
int x;
scanf("%d", &x);
if (x == -1) {
exit(0);
}
return x;
}
void solve() {
scanf("%d", &n);
for (int i = 1; i < n; ++i) {
a[i] = ask(i, i + 1);
}
vector<int> vc;
for (int i = 1; i <= n; ++i) {
bool flag = 1;
if (i > 1 && a[i - 1]) {
flag = 0;
}
if (i < n && !a[i]) {
flag = 0;
}
if (flag) {
vc.pb(i);
}
}
while ((int)vc.size() > 1) {
int mn = 1e9, p = -1;
for (int i = 0; i < (int)vc.size() - 1; ++i) {
int x = vc[i], y = vc[i + 1];
if (y - x < mn) {
mn = y - x;
p = i;
}
}
int x = vc[p], y = vc[p + 1];
if (ask(x, y) == ask(x + 1, y) + y - x) {
vc.erase(vc.begin() + p + 1);
} else {
vc.erase(vc.begin() + p);
}
}
printf("! %d\n", vc[0]);
fflush(stdout);
}
int main() {
int T = 1;
scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}