Code: Median Deletion

/**
 *    author:  tourist
 *    created: 28.03.2026 09:26:11
 **/
#undef _GLIBCXX_DEBUG

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

template <typename T, typename F> class SparseTable {
  public:
    int n;
    vector<vector<T>> mat;
    F func;

    SparseTable(const vector<T> &a, const F &f) : func(f) {
        n = static_cast<int>(a.size());
        int max_log = 32 - __builtin_clz(n);
        mat.resize(max_log);
        mat[0] = a;
        for (int j = 1; j < max_log; j++) {
            mat[j].resize(n - (1 << j) + 1);
            for (int i = 0; i <= n - (1 << j); i++) {
                mat[j][i] = func(mat[j - 1][i], mat[j - 1][i + (1 << (j - 1))]);
            }
        }
    }

    T get(int from, int to) const {
        assert(0 <= from && from <= to && to <= n - 1);
        int lg = 32 - __builtin_clz(to - from + 1) - 1;
        return func(mat[lg][from], mat[lg][to - (1 << lg) + 1]);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt;
    cin >> tt;
    while (tt--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            --a[i];
        }
        if (n == 1) {
            cout << 1 << '\n';
            continue;
        }
        vector<int> ans(n, -1);
        for (int rot = 0; rot < 2; rot++) {
            SparseTable smin(a, [&](int i, int j) { return min(i, j); });
            SparseTable smax(a, [&](int i, int j) { return max(i, j); });
            vector<int> pos(n);
            for (int i = 0; i < n; i++) {
                pos[a[i]] = i;
            }
            for (int i = 0; i < n; i++) {
                if (a[i] == 0 || a[i] == n - 1) {
                    ans[i] = 2;
                    continue;
                }
                int p0 = pos[0];
                int pn = pos[n - 1];
                if (p0 > i) {
                    continue;
                }
                if (pn < i) {
                    if (i == n - 1) {
                        ans[i] = 3;
                    } else {
                        int rvmin = smin.get(i + 1, n - 1);
                        int rvmax = smax.get(i + 1, n - 1);
                        int rpmin = (rvmin < a[i] ? pos[rvmin] : n);
                        int rpmax = (rvmax > a[i] ? pos[rvmax] : n);
                        if (p0 < pn) {
                            if (rpmin < rpmax) {
                                ans[i] = (rpmax == n ? 4 : 5);
                                int lvmin =
                                    (pn < i - 1 ? smin.get(pn + 1, i - 1) : n);
                                if (lvmin < rvmin) {
                                    ans[i] = 3;
                                }
                            } else {
                                ans[i] = 4;
                                if (rpmin == n) {
                                    ans[i] = 3;
                                } else {
                                    if (pn < i - 1) {
                                        int lvmin = smin.get(pn + 1, i - 1);
                                        int pvmin = pos[lvmin];
                                        if (pvmin < i - 1) {
                                            int lvmax =
                                                smax.get(pvmin + 1, i - 1);
                                            if (lvmin < rvmin &&
                                                lvmax > rvmax) {
                                                ans[i] = 3;
                                            }
                                        }
                                    }
                                }
                            }
                        } else {
                            if (rpmin > rpmax) {
                                ans[i] = (rpmin == n ? 4 : 5);
                                int lvmax =
                                    (p0 < i - 1 ? smax.get(p0 + 1, i - 1) : -1);
                                if (lvmax > rvmax) {
                                    ans[i] = 3;
                                }
                            } else {
                                ans[i] = 4;
                                if (rpmax == n) {
                                    ans[i] = 3;
                                } else {
                                    if (p0 < i - 1) {
                                        int lvmax = smax.get(p0 + 1, i - 1);
                                        int pvmax = pos[lvmax];
                                        if (pvmax < i - 1) {
                                            int lvmin =
                                                smin.get(pvmax + 1, i - 1);
                                            if (lvmin < rvmin &&
                                                lvmax > rvmax) {
                                                ans[i] = 3;
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                } else {
                    int lvmax = smax.get(0, i - 1);
                    int rvmin = smin.get(i + 1, n - 1);
                    int lpmax = (lvmax > a[i] ? pos[lvmax] : n);
                    int rpmin = (rvmin < a[i] ? pos[rvmin] : n);
                    if (lpmax == n && rpmin == n) {
                        ans[i] = 3;
                    } else {
                        if (lpmax == n) {
                            ans[i] = (rpmin < pn ? 3 : 4);
                        } else {
                            if (rpmin == n) {
                                ans[i] = (lpmax > p0 ? 3 : 4);
                            } else {
                                if (lpmax < p0 && rpmin > pn) {
                                    ans[i] = 5;
                                } else {
                                    if (lpmax < p0 || rpmin > pn) {
                                        ans[i] = 4;
                                    } else {
                                        ans[i] = 5;
                                        if (rpmin > i + 1) {
                                            if (smax.get(i + 1, rpmin - 1) >
                                                lvmax) {
                                                ans[i] = 3;
                                            }
                                        }
                                        if (lpmax < i - 1) {
                                            if (smin.get(lpmax + 1, i - 1) <
                                                rvmin) {
                                                ans[i] = 3;
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
            reverse(a.begin(), a.end());
            reverse(ans.begin(), ans.end());
        }
        for (int i = 0; i < n; i++) {
            cout << ans[i] << " \n"[i == n - 1];
        }
    }
    return 0;
}