首先，如果我们确定了 \(1, 2\) 或 \(n - 1, n\) 的位置，我们就能求出原排列。因为题目给了 \(p_1 < p_2\)，所以可以不考虑对称性。也就是说我们知道两个位置是 \(1, 2\) 或 \(n - 1, n\) 但不确定究竟是 \(1, 2\) 还是 \(n - 1, n\) 也可以。
然后，如果我们确定了一对挨得够近的一对数 \(i, j\)，用它们再去问剩下的，距离最大和次大的就是 \(1, 2\) 或 \(n - 1, n\)。（有个 corner case，若 \(p_i + p_j = n - 1\)，那么最大和次大值都有两个，注意判一下）
发现只要 \(|i - j| \le \frac{n - 4}{3}\)，距离最大和次大的就是 \(1, 2\) 或 \(n - 1, n\)。
上面用了 \(2(n - 2)\) 次操作，还剩下 \(424\) 次操作留给随机化。随机问一些 \((a, b, c)\)，如果回答 \(\le \frac{n - 4}{6}\)，那它们两两距离都 \(\le \frac{n - 4}{3}\)。操作次数很充裕，随不到的概率 \(< 10^{-10}\)。
code
// Problem: F. Median Queries
// Contest: Codeforces - Codeforces Round 723 (Div. 2)
// URL: https://codeforces.com/problemset/problem/1526/F
// Memory Limit: 256 MB
// Time Limit: 6000 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 = 100100;
int n, a[maxn];
vector<int> vc[maxn];
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
inline int ask(int x, int y, int z) {
printf("? %d %d %d\n", x, y, z);
fflush(stdout);
scanf("%d", &x);
return x;
}
void solve() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
vector<int>().swap(vc[i]);
}
int mn = 1e9, p = -1, q = -1;
for (int _ = 0; _ < 420; ++_) {
int x, y, z;
do {
x = rnd() % n + 1;
y = rnd() % n + 1;
z = rnd() % n + 1;
} while (x == y || x == z || y == z);
int t = ask(x, y, z);
if (t < mn) {
mn = t;
p = x;
q = y;
}
}
int mx = -1e9;
for (int i = 1; i <= n; ++i) {
if (i != p && i != q) {
int t = ask(i, p, q);
mx = max(mx, t);
vc[t].pb(i);
}
}
if ((int)vc[mx - 1].size() > 1 && ask(vc[mx][0], p, vc[mx - 1][0]) > ask(vc[mx][0], p, vc[mx - 1][1])) {
swap(vc[mx - 1][0], vc[mx - 1][1]);
}
p = vc[mx][0];
q = vc[mx - 1][0];
a[p] = 1;
a[q] = 2;
for (int i = 1; i <= n; ++i) {
if (i != p && i != q) {
a[i] = ask(i, p, q) + 2;
}
}
if (a[1] > a[2]) {
for (int i = 1; i <= n; ++i) {
a[i] = n - a[i] + 1;
}
}
printf("! ");
for (int i = 1; i <= n; ++i) {
printf("%d ", a[i]);
}
putchar('\n');
fflush(stdout);
scanf("%d", &n);
if (n == -1) {
exit(0);
}
}
int main() {
int T = 1;
scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}