#include <bits/stdc++.h>
using namespace std;
 
const int N = 1e6;
 
int main()
{
    int cases;
    scanf("%d", &cases);
    
    while (cases--) {
    	int n;
    	scanf ("%d", &n);
    	
    	vector <int> cnt(n + 1);
    	for (int i = 0; i < n; i++) {
    		int d;
    		scanf("%d", &d);
    		if (d < n) {
        		cnt[d]++;
    		} else {
    		    cnt[n] = N;
    		}
    	}
    	
    	bool good = true;
    	for (int i = 1; i <= n; i++) if (cnt[i] > cnt[i-1]) {
    	    good = false;
    	    break;
    	}
    	
    	puts(good ? "YES" : "NO");
    }
}

#include "bits/stdc++.h"
using namespace std;
 
int main()
{
	int t;
	scanf ("%d", &t);
	while (t--) {
		long long n, k, g;
		scanf ("%lld %lld %lld", &n, &k, &g);
 
		long long stolen = min((g - 1) / 2 * n, k * g);
		long long rest = (k * g - stolen) % g;
 
		if (rest > 0) {
		    stolen -= (g - 1) / 2;
		    long long last = ((g - 1) / 2 + rest) % g;
 
		    if (last * 2 < g) {
		        stolen += last;
		    } else {
		        stolen -= g - last;
		    }
		}
 
		printf ("%lld\n", stolen);
	}
}

#include <bits/stdc++.h>

int power(int a, int e) {
    if (e == 0) return 1;
    return e == 1 ? a : a * power(a, e-1);
}

void answer(int a, int b) {
    std::cout << a << " + " << b << " = " << a+b << std::endl;
}

int main() {
    using ll = long long;
    
    int t;
    std::cin >> t;
    while (t--) {

        int a, b, c;
        ll k;
        std::cin >> a >> b >> c >> k;
        
        bool good = false;
    
        for (int i = power(10, a-1); i < power(10, a); ++i) {
            int left = std::max(power(10, b-1), power(10, c-1) - i);
            int right = std::min(power(10, b)-1, power(10, c) - 1 - i);
            if (left > right) continue;
    
            int have = right - left + 1;
            if (k <= have) {
                answer(i, left + k - 1);
                good = true;
                break;
            }
    
            k -= have;
        }
    
        if (!good) std::cout << "-1" << std::endl;
    }

    return 0;
}

#include <bits/stdc++.h>
 
#define forr(i, n) for (int i = 0; i < n; i++)
#define FOREACH(iter, coll) for (auto iter = coll.begin(); iter != coll.end(); ++iter)
#define FOREACHR(iter, coll) for (auto iter = coll.rbegin(); iter != coll.rend(); ++iter)
#define lbound(P, K, FUN) ({auto SSS=P, PPP = P-1, KKK=(K)+1; while(PPP+1!=KKK) {SSS = (PPP+(KKK-PPP)/2); if(FUN(SSS)) KKK = SSS; else PPP = SSS;} PPP; })
#define testy()    \
    int _tests;    \
    cin >> _tests; \
    FOR(_test, 1, _tests)
#define CLEAR(tab) memset(tab, 0, sizeof(tab))
#define CONTAIN(el, coll) (coll.find(el) != coll.end())
#define FOR(i, a, b) for (int i = a; i <= b; i++)
#define FORD(i, a, b) for (int i = a; i >= b; i--)
#define MP make_pair
#define PB push_back
#define ff first
#define ss second
#define deb(X) X;
#define SIZE(coll) ((int)coll.size())
 
#define M 1000000007
#define INF 1000000007LL
 
using namespace std;
 
long long n, m, k;
long long poz_l, poz_p;
vector<long long> v;
 
long long policz_ile(long long strzal)
{
    while (poz_l < n && v[poz_l] < strzal)
        poz_l++;
    while (poz_p < n && v[poz_p] <= strzal)
        poz_p++;
 
    long long pocz = poz_p < k ? 0 : (strzal + v[poz_p - k]) / 2 + 1;
    long long kon = poz_l + k - 1 >= n ? m : (v[poz_l + k - 1] + strzal - 1) / 2;
 
    return max(0ll, kon - pocz + 1);
}
 
int solve()
{
    cin >> n >> m >> k;
    long long a;
    forr(i, n)
    {
        cin >> a;
        v.PB(a);
    }
    sort(v.begin(), v.end());
    v.PB(m + 1);
    long long res = policz_ile(0), best = 0;
    forr(i, n)
    {
        long long pocz = i == 0 ? max(0ll, v[i] - 2) : max(v[i] - 2, v[i - 1] + 3);
        long long kon = min(m, v[i] + 2);
        for (long long s = pocz; s <= kon; s++)
        {
            long long ile = policz_ile(s);
 
            if (ile > res)
            {
                res = ile;
                best = s;
            }
        }
    }
    cout << res << " " << best << '\n';
 
    return 0;
}
 
int main()
{
    std::ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    solve();
 
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

void solve()
{
    int k, n;
    scanf("%d", &k);

    n = 2 << k;

    vector <long long> input(n + 1);
    vector <int> memHighBits(1 << k, -1);
    vector <pair <int, int> > memLowBits(1 << k, {-1, -1});
    
    auto addInterval = [&memLowBits, &input](int s, int e) {
        const int remXor = input[e] ^ input[s - 1];
        auto &[os, oe] = memLowBits[remXor];

        if (os == -1) {
            os = s, oe = e;
            return false;
        }

        if (oe < s) {
            printf("%d %d %d %d\n", os, oe, s, e);
        } else {
            printf("%d %d %d %d\n", min(s, os), max(s, os) - 1, oe + 1, e);
        }

        return true;
    };

    memHighBits[0] = 0;
    for (int i = 1; i <= n; ++i) {
        scanf("%lld", &input[i]);
        input[i] ^= input[i - 1];
    }

    for (int i = 1; i <= n; ++i) {
        if (memHighBits[input[i] >> k] != -1) {
            if (addInterval(memHighBits[input[i] >> k] + 1, i)) {
                break;
            }
        }

        memHighBits[input[i] >> k] = i;
    }
}

int main()
{
    int cases;
    scanf("%d", &cases);

    while (cases--) {
        solve();
    }

    return 0;
}

#include<bits/stdc++.h>
using namespace std;
 
#define sz(s) (int)s.size()
#define all(s) s.begin(), s.end()
#define pb push_back
#define FOR(i, n) for(int i = 0; i < n; i++)
 
using vi = vector<int>;
using vvi = vector<vi>;
 
struct SCC {
    int cnt = 0;
    vi vis, scc_nr;
    vvi scc_list, DAG;
 
    SCC(){}
 
    SCC(vvi & G){
        // G is 0 indexed!
        int n = sz(G);
        vvi G_rev(n);
        vis = scc_nr = vi(n);
 
        vi postorder;
        for(int i = 0; i < n; i++)
            if(!vis[i])
                dfs_post(i, G, G_rev, postorder);
        
        vis = vi(n);
        while(sz(postorder)){
            auto akt = postorder.back();
            postorder.pop_back();
            if(!vis[akt]){
                DAG.emplace_back();
                scc_list.emplace_back();
                dfs_rev(akt, G_rev);
                cnt++;
            }
        }
 
        // optional
        for(int i = 0; i < sz(DAG); i++){
            sort(all(DAG[i]));
            DAG[i].resize(unique(all(DAG[i])) - DAG[i].begin());
        }
    }
 
    void dfs_post(int start, vvi & G, vvi & G_rev, vi & postorder){
        vis[start] = 1;
        for(auto & u : G[start]){
            G_rev[u].pb(start);
            if(!vis[u])
                dfs_post(u, G, G_rev, postorder);
        }
        
        postorder.pb(start);
    }
 
    void dfs_rev(int start, vvi & G_rev){
        vis[start] = true;
        scc_list.back().pb(start);
        scc_nr[start] = cnt;
 
        for(auto & u : G_rev[start])
            if(!vis[u])
                dfs_rev(u, G_rev);
            else if(scc_nr[u] != cnt)
                DAG[scc_nr[u]].pb(cnt);
    }
};
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    long long n, m, k;
    cin >> n >> m >> k;
 
    vvi G(n);
 
    set<pair<int, int>> edges;
    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        a--, b--;
        G[a].pb(b);
        edges.insert({a, b});
    }
 
    SCC scc(G);
    vi coloring(n, -1);
 
    auto try_coloring = [&](int num_col, const vi& group)
    {
        vi visited;
        function<bool(int)> dfs = [&](int start){
            visited.pb(start);
            
            bool good_coloring = true;
            for (auto & u : G[start])
            {
                if (scc.scc_nr[u] != scc.scc_nr[start])
                {
                    continue;
                }
                if (coloring[u] == -1)
                {
                    coloring[u] = (coloring[start] + 1) % num_col;
                    good_coloring &= dfs(u);
                }
                else
                {
                    good_coloring &= coloring[u] == (coloring[start] + 1) % num_col;
                }
 
                if (not good_coloring)
                {
                    break;    
                }
            }
 
            return good_coloring;
        };
 
        coloring[group[0]] = 0;
        if (not dfs(group[0]))
        {
            for (auto & u : visited)
            {
                coloring[u] = -1;
            }
            return vvi();
        }
        else
        {
            vvi ret(num_col);
            for (auto & u : visited)
            {
                ret[coloring[u]].push_back(u);
            }
            return ret;
        }
    };
 
    long long ans = 0;
    vi depths(n, -1);
 
    for (vi& group : scc.scc_list)
    {
        n = sz(group);
 
        if (n == 1 and edges.count({group[0], group[0]}) == 0)
        {
            continue;
        }
        int gcd = -1;
        function<void(int)> dfs_depths = [&](int start)
        {
            for (auto & u : G[start])
            {
                if (scc.scc_nr[u] != scc.scc_nr[start])
                {
                    continue;
                }
 
                if (depths[u] == -1)
                {
                    depths[u] = depths[start] + 1;
                    dfs_depths(u);
                }
                else {
                    int diff = abs(depths[u] - (depths[start] + 1));
                    if (diff)
                    {
                        if (gcd == -1)
                        {
                            gcd = diff;
                        }
                        else
                        {
                            gcd = __gcd(gcd, diff);
                        }
                    }
                }
            }
        };
 
        depths[group[0]] = 0;
        dfs_depths(group[0]);
        assert(gcd != -1);
 
        vvi by_color = try_coloring(gcd, group);
 
        assert(sz(by_color) != 0);
        if (k % gcd == 0)
        {
            FOR (i, gcd)
            {
                ans += sz(by_color[i]) + 1ll * sz(by_color[i]) * (sz(by_color[i]) - 1) / 2;
            }
        }
        else if (k % gcd * 2 == gcd)
        {
            FOR (i, gcd / 2)
            {
                ans += 1ll * sz(by_color[i]) * sz(by_color[i + gcd / 2]);
            }
        }
    }
    cout << ans << '\n';
}

#include <bits/stdc++.h>
 
using namespace std;
 
constexpr int MAX_M = 1000 + 7;
constexpr int PRECISION = 9;
constexpr long long MOD = 1e9 + 7;
 
long long mod_inv[MAX_M];
long long DP[MAX_M][MAX_M][2][2];
long long DPprob[MAX_M][MAX_M][2][2];
bool updated[MAX_M][MAX_M][2][2];
// DP[correct][incorrect][backspace][bad suffix]
 
long long calc_mod_inv(long long n)
{
    long long res = 1;
    long long exp = MOD - 2;
 
    while (exp)
    {
        if (exp & 1)
        {
            res = (res * n) % MOD;
        }
 
        exp >>= 1;
        n = (n * n) % MOD;
    }
 
    return res;
}
 
void calc_DP(int digits, int needed)
{
    DP[0][0][0][0] = 0;
    DPprob[0][0][0][0] = 1;
 
    struct ID
    {
        int x, y, z, s;
    };
 
    queue <ID> dp_queue;
    dp_queue.push({0, 0, 0, 0});
 
    while(!dp_queue.empty())
    {
        auto [x, y, z, s] = dp_queue.front();
        dp_queue.pop();
 
        if (updated[x][y][z][s])
        {
            continue;
        }
 
        updated[x][y][z][s] = true;
 
        long long left = digits + 1 - x - y - z;
        long long corr = needed - x;
        long long incorr = digits - needed - y;
        long long prob = DPprob[x][y][z][s];
 
        if (corr == 0 and s == 0)
        {
            // done
            continue;
        }
 
        // correct suffix
        if (s == 0)
        {
            if (corr > 0)
            {
                // found the one correct digit (no need to delete)
                long long opt_prob = (prob * mod_inv[left]) % MOD;
                DPprob[x + 1][y][z][0] = (DPprob[x + 1][y][z][0] + opt_prob) % MOD;
                DP[x + 1][y][z][0] = (DP[x + 1][y][z][0] + DP[x][y][z][0] * mod_inv[left]) % MOD;
 
                // found a needed but currently wrong digit (needs to be deleted)
                if (corr > 1)
                {
                    if (z == 0) // if backspace is not known, the suffix is bad
                    {
                        long long opt_prob = ((prob * (corr - 1) % MOD) * mod_inv[left]) % MOD;
                        DPprob[x + 1][y][z][1] = (DPprob[x + 1][y][z][1] + opt_prob) % MOD;
 
                        DP[x + 1][y][z][1] = (DP[x + 1][y][z][1] + ((corr - 1) * mod_inv[left] % MOD) * DP[x][y][z][0] + 2 * opt_prob) % MOD;
                        dp_queue.push({x + 1, y, z, 1});
                    }
                    else // if backspace is known, the suffix can be instantly repaired
                    {
                        long long opt_prob = ((prob * (corr - 1) % MOD) * mod_inv[left]) % MOD;
                        DPprob[x + 1][y][z][0] = (DPprob[x + 1][y][z][0] + opt_prob) % MOD;
                        DP[x + 1][y][z][0] = (DP[x + 1][y][z][0] + ((corr - 1) * mod_inv[left] % MOD) * DP[x][y][z][0] + 2 * opt_prob) % MOD;
                    }
                }
 
                dp_queue.push({x + 1, y, z, 0});
            }
 
            if (incorr > 0)
            {
                // found an incorrect digit
                if (z == 0)
                {
                    long long opt_prob = (prob * incorr % MOD) * mod_inv[left] % MOD;
                    DPprob[x][y + 1][z][1] = (DPprob[x][y + 1][z][1] + opt_prob) % MOD;
                    DP[x][y + 1][z][1] = (DP[x][y + 1][z][1] + (incorr * mod_inv[left] % MOD) * DP[x][y][z][0] + 2 * opt_prob) % MOD;
                    dp_queue.push({x, y + 1, z, 1});
                }
                else // suffix can be repaired
                {
                    long long opt_prob = ((prob * incorr % MOD) * mod_inv[left]) % MOD;
                    DPprob[x][y + 1][z][0] = (DPprob[x][y + 1][z][0] + opt_prob) % MOD;
                    DP[x][y + 1][z][0] = (DP[x][y + 1][z][0] + (incorr * mod_inv[left] % MOD) * DP[x][y][z][0] + 2 * opt_prob) % MOD;
                    dp_queue.push({x, y + 1, z, 0});
                }
            }
 
            if (z == 0)
            {
                if (x > 0) // deleted correct digit
                {
                    long long opt_prob = prob * mod_inv[left] % MOD;
                    DPprob[x][y][1][0] = (DPprob[x][y][1][0] + opt_prob) % MOD;
                    DP[x][y][1][0] = (DP[x][y][1][0] + mod_inv[left] * DP[x][y][0][0] + 2 * opt_prob) % MOD;
                }
                else // deleted nothing
                {
                    long long opt_prob = prob * mod_inv[left] % MOD;
                    DPprob[x][y][1][0] = (DPprob[x][y][1][0] + opt_prob) % MOD;
                    DP[x][y][1][0] = (DP[x][y][1][0] + mod_inv[left] * DP[x][y][0][0] + opt_prob) % MOD;
                }
 
                dp_queue.push({x, y, 1, 0});
            }
        }
 
        if (s == 1)
        {
            if (corr > 0)
            {
                // found a needed but currently wrong digit (needs to be deleted)
                long long opt_prob = (prob * corr % MOD) * mod_inv[left] % MOD;
                DPprob[x + 1][y][z][1] = (DPprob[x + 1][y][z][1] + opt_prob) % MOD;
                DP[x + 1][y][z][1] = (DP[x + 1][y][z][1] + (corr * mod_inv[left] % MOD) * DP[x][y][z][1] + 2 * opt_prob) % MOD;
                dp_queue.push({x + 1, y, z, 1});
            }
 
            if (incorr > 0)
            {
                // found an incorrect digit
                long long opt_prob = (prob * incorr % MOD) * mod_inv[left] % MOD;
                DPprob[x][y + 1][z][1] = (DPprob[x][y + 1][z][1] + opt_prob) % MOD;
                DP[x][y + 1][z][1] = (DP[x][y + 1][z][1] + (incorr * mod_inv[left] % MOD) * DP[x][y][z][1] + 2 * opt_prob) % MOD;
                dp_queue.push({x, y + 1, z, 1});
            }
 
            if (z == 0)
            {
                // deleted bad suffix
                long long opt_prob = prob * mod_inv[left] % MOD;
                DPprob[x][y][1][0] = (DPprob[x][y][1][0] + opt_prob) % MOD;
                DP[x][y][1][0] = (DP[x][y][1][0] + mod_inv[left] * DP[x][y][0][1]) % MOD;
                dp_queue.push({x, y, 1, 0});
            }
        }
    }
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    mod_inv[0] = 1;
    for (int i = 1; i < MAX_M; ++i) {
        mod_inv[i] = calc_mod_inv(i);
        assert (mod_inv[i] * i % MOD == 1);
    }
 
    int n, m;
    cin >> n >> m;
 
    set <int> different_digits;
 
    for (int i = 0; i < n; ++i)
    {
        int p;
        cin >> p;
 
        different_digits.insert(p);
    }
 
    int needed = different_digits.size();
 
    calc_DP(m, needed);
 
    long long result = 0;
 
    for (int i = 0; i <= MAX_M; ++i)
    {
        result = (result + DP[needed][i][0][0]) % MOD;
        result = (result + DP[needed][i][1][0]) % MOD;
    }
 
    cout << (result + n) % MOD << "\n";
 
    return 0;
}

#include <bits/stdc++.h>

#define forr(i, n) for (int i = 0; i < n; i++)
#define FOREACH(iter, coll) for (auto iter = coll.begin(); iter != coll.end(); ++iter)
#define FOREACHR(iter, coll) for (auto iter = coll.rbegin(); iter != coll.rend(); ++iter)
#define lbound(P, K, FUN) ({auto SSS=P, PPP = P-1, KKK=(K)+1; while(PPP+1!=KKK) {SSS = (PPP+(KKK-PPP)/2); if(FUN(SSS)) KKK = SSS; else PPP = SSS;} PPP; })
#define testy()    \
    int _tests;    \
    cin >> _tests; \
    FOR(_test, 1, _tests)
#define CLEAR(tab) memset(tab, 0, sizeof(tab))
#define CONTAIN(el, coll) (coll.find(el) != coll.end())
#define FOR(i, a, b) for (int i = a; i <= b; i++)
#define FORD(i, a, b) for (int i = a; i >= b; i--)
#define MP make_pair
#define PB push_back
#define ff first
#define ss second
#define deb(X) X;
#define SIZE(coll) ((int)coll.size())

using namespace std;

const int MXN = 1007;
int n, m;
vector<int> G[MXN];
bitset<MXN> bs[MXN], edge[MXN];

// MATCHING

const int MXM = 1007 * 2;
int skojX[MXM], skojY[MXM];
bool vis[MXM];

bool dfs_m(int x)
{
    vis[x] = 1;
    FOREACH(it, G[x])
    if (!skojY[*it] || (!vis[skojY[*it]] && dfs_m(skojY[*it])))
    {
        skojX[x] = *it;
        skojY[*it] = x;
        return 1;
    }
    return 0;
}

bool skoj()
{
    int czy = 1;
    int res = 0;
    while (czy)
    {
        czy = 0;
        CLEAR(vis);
        FOR(i, 1, n)
        if (!vis[i] && !skojX[i] && dfs_m(i))
        {
            czy = 1;
            res++;
        }
    }
    return res == n;
}

// END OF MATCHING

void dfs(int nr, bitset<MXN> &visited, bitset<MXN> &to_visit)
{
    visited[nr] = 1;
    to_visit[nr] = 0;
    to_visit = to_visit | (edge[nr] & (~visited));
    for (int i = to_visit._Find_first(); i < SIZE(to_visit); i = to_visit._Find_next(i))
        dfs(i, visited, to_visit);
}

int solve()
{
    cin >> n >> m;
    forr(i, m)
    {
        int a, b;
        cin >> a >> b;
        G[a].PB(b);
    }

    int rres = skoj();
    if (rres)
    {
        FOR(i, 1, n)
        {
            for (auto j : G[i])
            {
                edge[i][skojY[j]] = 1;
            }
        }
        unordered_map<bitset<MXN>, vector<int>> mapa;
        vector<pair<int, int>> vec, res;
        FOR(i, 1, n)
        {
            bitset<MXN> to_visit;
            dfs(i, bs[i], to_visit);
            mapa[bs[i]].PB(i);
        }

        for (auto p : mapa)
        {
            vector<int> l = p.ss;
            vec.PB({bs[l[0]].count(), l[0]});
            if (l.size() == 1)
            {
                res.PB({l[0], l[0]});
                continue;
            }
            for (int i = 0; i < SIZE(l); i++)
            {
                res.PB({l[i], l[i]});
                res.PB({l[i], l[(i + 1) % SIZE(l)]});
            }
        }
        sort(vec.begin(), vec.end());
        forr(i, SIZE(vec))
        {
            int nr = vec[i].ss;
            bitset<MXN> b;
            for (int j = i - 1; j >= 0; j--)
                if (vec[j].ff < vec[i].ff)
                {
                    int nr2 = vec[j].ss;
                    if (bs[nr][nr2] && !b[nr2])
                    {
                        b |= bs[nr2];
                        res.PB({nr, nr2});
                    }
                }
        }

        cout << "YES" << '\n';
        cout << res.size() << '\n';
        for (auto p : res)
            cout << p.ff << " " << p.ss + n << '\n';
    }
    else
    {
        CLEAR(vis);
        FOR(i, 1, n)
        {
            if (skojX[i] == 0)
            {
                dfs_m(i);
                break;
            }
        }
        vector<int> v;
        FOR(i, 1, n)
        {
            if (vis[i])
                v.PB(i);
        }
        cout << "NO" << '\n';
        cout << v.size() << '\n';
        for (auto el : v)
            cout << el << " ";
        cout << '\n';
    }

    return 0;
}

int main()
{
    std::ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    solve();

    return 0;
}