Bowser's Castle (Hard Version)

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

void setIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

const int SHIFT = 100000;
const int INFV = 100000;

int n;

int readInt() {
    int x;
    if (!(cin >> x)) exit(0);
    if (x == -1) exit(0);
    return x;
}

struct Node {
    int l, r;
    bool isMax, leaf;
    vector<Node*> child;

    Node(int L, int R) : l(L), r(R), isMax(false), leaf(true) {}

    Node(int L, int R, bool op, vector<Node*> kids)
        : l(L), r(R), isMax(op), leaf(false), child(kids) {}

    void flatten() {
        if (leaf) return;
        vector<Node*> nxt;
        for (Node* v : child) {
            v->flatten();
            if (!v->leaf && v->isMax == isMax) {
                for (Node* u : v->child) nxt.push_back(u);
            } else {
                nxt.push_back(v);
            }
        }
        child.swap(nxt);
    }

    int eval(const vector<int>& x) const {
        if (leaf) return x[l];
        int ans = isMax ? INT_MIN : INT_MAX;
        for (Node* v : child) {
            int got = v->eval(x);
            if (isMax) ans = max(ans, got);
            else ans = min(ans, got);
        }
        return ans;
    }
};

int ask(const vector<int>& q) {
    cout << "?";
    for (int i = 1; i <= n; i++) {
        int v = q[i];
        v = max(-SHIFT, min(SHIFT, v));
        cout << ' ' << v + SHIFT + 1;
    }
    cout << endl;

    int ans = readInt();
    return ans - SHIFT - 1;
}

Node* recover(int l, int r, const vector<int>& defaults) {
    if (l == r) return new Node(l, r);

    vector<int> q = defaults;
    for (int i = l; i <= r; i++) q[i] = i;
    int p = ask(q);

    if (p == r) {
        vector<int> nd = defaults;
        nd[r] = -INFV;
        Node* rest = recover(l, r - 1, nd);
        Node* res = new Node(l, r, true, {rest, new Node(r, r)});
        res->flatten();
        return res;
    }

    if (p == l) {
        vector<int> nd = defaults;
        nd[l] = INFV;
        Node* rest = recover(l + 1, r, nd);
        Node* res = new Node(l, r, false, {new Node(l, l), rest});
        res->flatten();
        return res;
    }

    vector<int> leftDefaults = defaults;
    for (int i = p + 1; i <= r; i++) leftDefaults[i] = INFV;

    vector<int> rightDefaults = defaults;
    for (int i = l; i < p; i++) rightDefaults[i] = -INFV;

    Node* left = recover(l, p, leftDefaults);
    left->flatten();
    vector<Node*> leftPieces = left->child;
    leftPieces.pop_back();

    Node* right = recover(p, r, rightDefaults);
    right->flatten();
    vector<Node*> rightPieces = right->child;
    reverse(rightPieces.begin(), rightPieces.end());
    rightPieces.pop_back();

    Node* mid = new Node(p, p);

    while (!leftPieces.empty() && !rightPieces.empty()) {
        Node* A = leftPieces.back();
        Node* B = rightPieces.back();

        vector<int> query = defaults;
        for (int i = l; i < A->l; i++) query[i] = 0;
        for (int i = A->l; i <= A->r; i++) query[i] = 3;
        for (int i = A->r + 1; i < B->l; i++) query[i] = 2;
        for (int i = B->l; i <= B->r; i++) query[i] = 1;
        for (int i = B->r + 1; i <= r; i++) query[i] = 4;

        int got = ask(query);
        if (got == 1) {
            mid = new Node(A->l, mid->r, true, {A, mid});
            mid->flatten();
            leftPieces.pop_back();
        } else {
            mid = new Node(mid->l, B->r, false, {mid, B});
            mid->flatten();
            rightPieces.pop_back();
        }
    }

    while (!leftPieces.empty()) {
        Node* A = leftPieces.back();
        leftPieces.pop_back();
        mid = new Node(A->l, mid->r, true, {A, mid});
        mid->flatten();
    }

    while (!rightPieces.empty()) {
        Node* B = rightPieces.back();
        rightPieces.pop_back();
        mid = new Node(mid->l, B->r, false, {mid, B});
        mid->flatten();
    }

    return mid;
}

int main() {
    setIO();

    int T = readInt();
    while (T--) {
        n = readInt();

        vector<int> defaults(n + 1, 0);
        Node* root = recover(1, n, defaults);

        cout << "!" << endl;

        while (true) {
            vector<int> x(n + 1);
            x[1] = readInt();
            if (x[1] == 0) break;
            for (int i = 2; i <= n; i++) x[i] = readInt();
            cout << root->eval(x) << endl;
        }
    }

    return 0;
}