真是个沙比提，比赛的时候也想出来了，但是因为太迷糊了没写完
首先我们先考虑如何确定下最大值所在的位置。
执行询问$max(min(n-1,p_i),min(n,p_{i+1}))$，这个询问实际上等价于$max(min(n-1,p_i),p_{i+1})$。
- 如果结果是n，那么说明$p_{i+1}=n$（很显然，max里第一项不会超过n-1）。
- 如果结果比n-1要小，那么说明$p_i$和$p_{i+1}$都不是n。
- 如果结果是n-1，那么就要讨论下了。这个时候n可能出现在这两个数里，也可能没出现。
我们再构造另一个询问：$min(max(n-1,p_i),max(n,p_{i+1}))$，显然这个询问等价于$max(n-1,p_i)$，所以我们可以利用这个询问来检查$p_i$的值是不是n。
在找到最大值的位置，设它为$maxpos$，那么我们对于每一个$i\neq maxpos$，构造询问$min(max(1,p_i),max(2,p_{maxpos}))$，这个询问等价于$p_i$，然后就可以求出来每个位置的值了。
#include <algorithm>
#include <iostream>
using std::cin;
using std::cout;
using std::endl;
using int_t = long long;
int_t result[int_t(1e5)];
int main() {
std::ios::sync_with_stdio(false);
int_t T;
cin >> T;
while (T--) {
int_t n;
cin >> n;
int_t maxpos = -1;
const auto check = [&](int_t i, int_t j) {
cout << "? 1 " << i << " " << j << " " << n - 1 << endl;
int_t x;
cin >> x;
if (x == n) {
maxpos = j;
return;
}
if (x < n - 1)
return;
// x==n-1
for (int_t _ = 1; _ <= 2; _++) {
cout << "? 2 " << i << " " << j << " "<< n - 1 << endl;
cin >> x;
if (x == n) {
maxpos = i;
}
std::swap(i, j);
}
};
for (int_t i = 1; i <= n && i + 1 <= n && maxpos == -1; i += 2) {
int_t j = i + 1;
check(i, j);
}
if (maxpos == -1) {
maxpos = n;
}
result[maxpos] = n;
for (int_t i = 1; i <= n; i++) {
if (i == maxpos)
continue;
cout << "? 2 " << i << " " << maxpos << " 1" << endl;
;
int_t x;
cin >> x;
result[i] = x;
}
cout << "! ";
for (int_t i = 1; i <= n; i++) {
cout << result[i] << " ";
}
cout << endl;
}
return 0;
}