#include "checkpoint.h"

#include <algorithm>
#include <cassert>
#include <iostream>
#include <random>
#include <utility>
#include <vector>

static int n;
static std::vector<int> p, pos;
static int verbose = 0;
static int query_count = 0;

int min_value(int i, int j) {
    if (min(i, j) <= 0 || max(i, j) > n) {
        std::cout << "Incorrect operation i=" << save_i << ", j=" << save_j << std::endl;
        exit(0);
    }

    ++query_count;
    int save_i = i, save_j = j;
    i = pos[i], j = pos[j];
    if (i > j) std::swap(i, j);
    int res = n;
    if (j - i > n - j + i) {
        for (int t = j; t < n; ++t) res = std::min(res, p[t]);
        for (int t = 0; t <= i; ++t) res = std::min(res, p[t]);
    } else {
        for (int t = i; t <= j; ++t) res = std::min(res, p[t]);
    }

    if (verbose >= 2) {
        std::cout << "min_value(" << save_i << ", " << save_j << ") --> " << res << std::endl;
    }
    return res;
}

// Если компиляция из командной строки вызывает у вас сложности, напишите функцию guess здесь.
// If you can not compile using command line, write function guess here.

int main() {
    int t;
    std::cin >> t;

    std::mt19937 rng(1337228);

    for (int tid = 1; tid <= t; ++tid) {
        if (verbose >= 1) {
            std::cout << "Run testcase #" << tid << std::endl;
        }

        std::cin >> n;
        if (n % 2 == 0) {
            std::cout << "Incorrect testase n=" << n << " is even" << std::endl;
            exit(0);
        }

        p.resize(n);
        for (int i = 0; i < n; ++i) {
            std::cin >> p[i];
            if (i == 0 && p[i] == -1) {
                for (int j = 0; j < n; ++j) p[j] = j + 1;
                std::shuffle(p.begin(), p.end(), rng);
                break;
            }
        }
        pos.resize(n+1);
        for (int i = 0; i < n; ++i) pos[p[i]] = i;

        if (verbose >= 1) {
            std::cout << "p =";
            for (int x : p) std::cout << " " << x;
            std::cout << std::endl;
        }

        query_count = 0;
        std::vector<int> q = guess(n);

        if (verbose >= 1) {
            std::cout << "q =";
            for (int x : q) std::cout << " " << x;
            std::cout << std::endl;
        }
        std::cout << "queries count => " << query_count << std::endl;
    }
}