#include<bits/stdc++.h>
using namespace std;
vector<string> gr;
int cnt = 0;
vector<int> perm;
vector<vector<int>> mem;
bool que(int u, int v) {
u = perm[u], v = perm[v];
if(~mem[u][v]) return mem[u][v];
cnt++;
// cout << "? " << u + 1 << ' ' << v + 1 << endl;
// char c; cin >> c;
char c = (gr[u][v] == '1' ? '>' : '<');
mem[u][v] = c == '>';
mem[v][u] = !mem[u][v];
return mem[u][v];
}
void ans(vector<int> c) {
cout << "! ";
for(auto x : c) cout << x + 1 << ' ';
cout << endl;
}
void solve4() {
int n = 4;
mem.assign(n, vector<int> (n, -1));
vector<int> c(n);
iota(c.begin(), c.end(), 0);
do {
bool ok = 1;
for(int i = 0; i < n; ++i) {
ok &= que(c[i], c[(i + 1) % n]);
}
if(ok) {
ans(c);
return;
}
} while(next_permutation(c.begin(), c.end()));
}
vector<int> merge(vector<int> a, vector<int> b) {
if(que(a.back(), b[0])) {
for(auto x : b) a.push_back(x);
return a;
}
else if(que(b.back(), a[0])){
for(auto x : a) b.push_back(x);
return b;
}
return {-1};
}
void solve(int n) {
random_shuffle(perm.begin(), perm.end());
mem.assign(n, vector<int> (n, -1));
vector<vector<int>> cu;
for(int i = 0; i < n; ++i) cu.push_back({i});
for(int i = 0; i + 1 < (int)cu.size(); ++i) {
auto z = merge(cu[i], cu[i + 1]);
if(z[0] == -1) continue;
cu[i] = z;
cu.erase(cu.begin() + i + 1);
}
for(int _ = 0; _ < 2000 && cu.size() > 1; ++_) {
int a = rand() % (int)cu.size();
int b = rand() % (int)cu.size();
if(a == b) continue;
auto z = merge(cu[a], cu[b]);
if(z[0] == -1) continue;
cu[a] = z;
cu.erase(cu.begin() + b);
}
sort(cu.begin(), cu.end(), [&](auto a, auto b) { return a.size() > b.size(); });
while(cu.size() > 1) {
for(int i = 0; i < (int)cu[0].size(); ++i) {
if(que(cu[0][i], cu.back()[0]) && que(cu.back().back(), cu[0][i + 1])) {
while(cu.back().size()) {
cu[0].insert(cu[0].begin() + i + 1, cu.back().back());
cu.back().pop_back();
}
break;
}
}
cu.pop_back();
}
auto c = cu[0];
int ls = (int)c.size() - 1;
while(que(c[0], c[ls])) ls--;
ls++;
if(ls < n) {
for(int i = 0; i < ls; ++i) {
if(que(c[i], c[ls]) && que(c.back(), c[i + 1])) {
for(int j = 0; j < (int)c.size() - ls; ++j) {
c.insert(c.begin() + i + 1, c.back());
c.pop_back();
}
break;
}
}
}
for(int i = 0; i < n; ++i) assert(que(c[i], c[(i + 1) % n]));
// ans(c);
}
int sim(int _, int n, int t) {
srand(_);
cnt = 0;
// int n, t; cin >> n >> t;
perm.resize(n);
iota(perm.begin(), perm.end(), 0);
if(n == 4) {
gr = {"0110", "0011", "0001", "1000"};
cout << "0110\n0011\n0001\n1000" << endl;
while(t--) {
solve4();
}
return 0;
}
gr.resize(n, string(n, '0'));
for(int i = 0; i < n; ++i) {
for(int j = 0; j < n; ++j) {
if(i == j) continue;
int x = rand() & 1;
gr[i][j] = '1' - x;
gr[j][i] = '0' + x;
}
}
// for(auto x : gr) cout << x << endl;
while(t--) solve(n);
return cnt;
}
int main() {
pair<int, int> bes = {1 << 30, -1};
for(int i = 0; i < 2000; ++i) {
pair<int, int> cu = make_pair(sim(i, 500, 200), i);
bes = min(bes, cu);
if(i % 100 == 0) {
cerr << bes.first << ' ' << bes.second << '\n';
}
}
cout << bes.first << ' ' << bes.second << '\n';
}
