Heapify 1

    1#include <bits/stdc++.h>
    2using namespace std;
    3using ll = long long;
    4const int inf = 1e9;
    5const long long INF = 1e17; //❄️
    6vector<int> parent;
    7int find(int x) {
    8    return x == parent[x] ? x : parent[x] = find(parent[x]);
    9}
    10void unite(int x, int y) {
    11    x = find(x); y = find(y);
    12    parent[x] = y;
    13}
    14void solve() {
    15    int n; cin >> n;
    16    parent.resize(n + 1);
    17    for (int i = 1; i <= n; i++) parent[i] = i;
    18    vector<int> v(n + 1);
    19    for (int i = 1; i <= n; i++) {
    20        cin >> v[i];
    21    }
    22    for (int i = 1; i <= n / 2; i++) {
    23        unite(i, 2 * i);
    24    }
    25    unordered_map<int, vector<int>> indx, val;
    26    for (int i = 1; i <= n; i++) {
    27        int p = find(i);
    28        indx[p].push_back(i);
    29        val[p].push_back(v[i]);
    30    }
    31    for (auto &a : indx) {
    32        auto &index = a.second;
    33        auto &value = val[a.first];
    34        sort(index.begin(), index.end());
    35        sort(value.begin(), value.end());
    36        if (index != value) {
    37            cout << "No" << '\n';
    38            return;
    39        }
    40    }
    41    cout << "Yes" << '\n';
    42}
    43int main() {
    44    ios::sync_with_stdio(0); cin.tie(0); 
    45    int t; cin >> t;
    46    while (t--) {
    47        solve();
    48    }
    49    return 0;
    50}