#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define x first
#define y second
#define LL long long
#define LD long double
#define Complex complex<double>
#define y1 ___y1
#define next ___next
#define left ___left
#define right ___right
#define pii pair<int, int>
#define pll pair<LL, LL>
#define pdd pair<double, double>
#define pldld pair<LD, LD>
#define vi vector<int>
#define vl vector<LL>
#define vii vector<pii>
#define vll vector<pll>
#define PQ priority_queue
#define ffo fflush(stdout)
#define gch getchar()
#define e (int)(1e9 + 7)
#define e2 (double)2.71828182846
#define pi (double)3.14159265358979
#define ri(X) scanf("%d", &(X))
#define rii(X, Y) scanf("%d%d", &(X), &(Y))
#define riii(X, Y, Z) scanf("%d%d%d", &(X), &(Y), &(Z))
#define rl(X) scanf("%lld", &(X))
#define rll(X, Y) scanf("%lld%lld", &(X), &(Y))
#define rlll(X, Y, Z) scanf("%lld%lld%lld", &(X), &(Y), &(Z))
#define printi(X) printf("%d", (int)(X))
#define printii(X, Y) printf("%d %d", (int)(X), (int)(Y))
#define printiii(X, Y, Z) printf("%d %d %d", (int)(X), (int)(Y), (int)(Z))
#define printl(X) printf("%lld", (LL)(X))
#define printll(X, Y) printf("%lld %lld", (LL)(X), (LL)(Y))
#define printlll(X, Y, Z) printf("%lld %lld %lld", (LL)(X), (LL)(Y), (LL)(Z))
#define enter printf("\n")
#define space printf(" ")
struct matrix {
    int sz;
    LL a[105][105];
    matrix& operator = (const matrix &T) {
        sz = T.sz;
        for (int i = 1; i <= sz; i++) {
            for (int j = 1; j <= sz; j++) {
                a[i][j] = T.a[i][j];
            }
        }
        return *this;
    }
    matrix operator + (const matrix &T) const {
        matrix ans;
        ans.sz = sz;
        for (int i = 1; i <= sz; i++) {
            for (int j = 1; j <= sz; j++) {
                ans.a[i][j] = a[i][j] + T.a[i][j];
                ans.a[i][j] %= e;
            }
        }
        return ans;
    }
    matrix operator * (const matrix &T) const {
        matrix ans;
        ans.sz = sz;
        for (int i = 1; i <= sz; i++) {
            for (int j = 1; j <= sz; j++) {
                ans.a[i][j] = 0;
                for (int k = 1; k <= sz; k++) {
                    ans.a[i][j] += a[i][k] * T.a[k][j];
                    ans.a[i][j] %= e;
                }
            }
        }
        return ans;
    }
    matrix I() {
        matrix ans;
        ans.sz = sz;
        for (int i = 1; i <= sz; i++) {
            for (int j = 1; j <= sz; j++) {
                if (i == j) ans.a[i][j] = 1;
                else ans.a[i][j] = 0;
            }
        }
        return ans;
    }
    matrix power(LL p) {
        if (p == 0) return I();
        if (p == 1) return *this;
        matrix tmp = power(p / 2);
        if (p % 2) tmp = tmp * tmp * (*this);
        else tmp = tmp * tmp;
        return tmp;
    }
    void print() {
        for (int i = 1; i <= sz; i++) {
            for (int j = 1; j <= sz; j++) {
                printf(j == sz? "%lld\n" : "%lld ", a[i][j]);
            }
        }
        return;
    }
};
struct polynomial {
    vector<Complex> v;
    int sz;
    polynomial operator * (const polynomial &T) const {
        polynomial ans;
        if (sz >= T.sz) {
            ans = *this;
            for (int i = 0; i < T.sz; i++) {
                ans.v[i] *= T.v[i];
            }
        }
        else {
            ans = T;
            for (int i = 0; i < sz; i++) {
                ans.v[i] *= v[i];
            }
        }
        return ans;
    }
};
polynomial FFT(polynomial a) {
    if (a.sz <= 1) return a;
    polynomial even, odd;
    even.sz = odd.sz = 0;
    for (int i = 0; i < a.sz; i += 2) {
        even.v.pb(a.v[i]);
        even.sz++;
    }
    for (int i = 1; i < a.sz; i += 2) {
        odd.v.pb(a.v[i]);
        odd.sz++;
    }
    polynomial Even = FFT(even);
    polynomial Odd = FFT(odd);
    polynomial ans;
    ans.sz = a.sz;
    for (int i = 0; i < ans.sz; i++) {
        ans.v.pb(0);
    }
    for (int i = 0; i < a.sz / 2; i++) {
        Complex w = polar(1.0, -2 * pi * i / a.sz) * Odd.v[i];
        ans.v[i] = Even.v[i] + w;
        ans.v[i + a.sz / 2] = Even.v[i] - w;
    }
    return ans;
}
polynomial IFFT(polynomial a) {
    for (int i = 0; i < a.sz; i++) {
        a.v[i] = conj(a.v[i]);
    }
    polynomial ans = FFT(a);
    for (int i = 0; i < a.sz; i++) {
        ans.v[i] = conj(ans.v[i]);
        ans.v[i] /= ans.sz;
    }
    return ans;
}
struct polygon {
    int n;
    pii a[1005];
    double area() {
        double d1 = 0, d2 = 0;
        for (int i = 0; i < n; i++) {
            d1 += a[i].x * a[(i + 1) % n].y;
            d2 += a[(i + 1) % n].x * a[i].y;
        }
        return (d1 - d2) / 2;
    }
    bool inside(pldld p) {
        int ct = 0;
        LD d;
        pldld p1 = a[0];
        for (int i = 1; i <= n; i++) {
            pldld p2 = a[i % n];
            if (p.y > min(p1.y, p2.y) && p.y <= max(p1.y, p2.y) && p.x <= max(p1.x, p2.x) && p1.y != p2.y) {
                d = (p.y - p1.y) * (p2.x - p1.x) / (p2.y - p1.y) + p1.x;
                if (p1.x == p2.x || p.x <= d) ct++;
            }
            p1 = p2;
        }
        return ct % 2;
    }
};
struct segtree {
    int l, r, mid;
    LL val = 0, lazy = 0;
    segtree *lc, *rc;
    segtree(int L, int R) {
        l = L;
        r = R;
        mid = (l + r) / 2;
        if (l != r) {
            lc = new segtree(l, mid);
            rc = new segtree(mid + 1, r);
        }
    }
    void apply(LL X) {
        val += X;
        // val += X * (r - l + 1);
        lazy += X;
    }
    void push() {
        if (l == r) return;
        lc->apply(lazy);
        rc->apply(lazy);
        lazy = 0;
    }
    void update(int L, int R, LL X) {
        push();
        if (l == L && r == R) {
            apply(X);
            return;
        }
        else if (R <= mid) lc->update(L, R, X);
        else if (L >= mid + 1) rc->update(L, R, X);
        else {
            lc->update(L, mid, X);
            rc->update(mid + 1, R, X);
        }
        val = min(lc->val, rc->val);
        // val = lc->val + rc->val;
    }
    LL query(int L, int R) {
        push();
        if (l == L && r == R) return val;
        else if (R <= mid) return lc->query(L, R);
        else if (L >= mid + 1) return rc->query(L, R);
        else {
            return min(lc->query(L, mid), rc->query(mid + 1, R));
            // return lc->query(L, mid) + rc->query(mid + 1, R);
        }
    }
    //segroot = new segtree(0, n - 1)
} *segroot;
LL power(LL a, LL p) {
    if (p == 0) return 1;
    if (p == 1) return a;
    LL tmp = power(a, p / 2);
    if (p % 2) tmp = tmp * tmp % e * a;
    else tmp *= tmp;
    return tmp % e;
}
struct node {
    int num;
    int l, r;
};

int T;
int n, a[200005];
node p[200005];

void solve(int CASE) {
    ri(n);
    for (int i = 1; i <= n; i++) {
        ri(a[i]);
    }
    int small = 0;
    int big = 0;
    int sz = 3;
    p[3].l = 1;
    p[3].r = 2;
    p[3].num = a[1];
    int pl = 3;
    for (int i = 2; i <= n; i++) {
        if (a[i] == p[pl].num) {
        }
        else if (a[i] > p[pl].num) {
            if (p[pl].r == 2) {
                int next = ++sz;
                p[pl].r = next;
                p[next].num = a[i];
                p[next].l = pl;
                p[next].r = 2;
                pl = next;
            }
            else if (p[p[pl].r].num == a[i]) {
                pl = p[pl].r;
            }
            else if (p[p[pl].r].num > a[i]) {
                int next = ++sz;
                p[next].num = a[i];
                p[next].l = pl;
                p[next].r = p[pl].r;
                p[p[next].r].l = next;
                p[pl].r = next;
                pl = next;
            }
            else {
                printf("NO\n");
                return;
            }
        }
        else {
            if (p[pl].l == 1) {
                int next = ++sz;
                p[pl].l = next;
                p[next].num = a[i];
                p[next].l = 1;
                p[next].r = pl;
                pl = next;
            }
            else if (p[p[pl].l].num == a[i]) {
                pl = p[pl].l;
            }
            else if (p[p[pl].l].num < a[i]) {
                int next = ++sz;
                p[next].num = a[i];
                p[next].r = pl;
                p[next].l = p[pl].l;
                p[p[next].l].r = next;
                p[pl].l = next;
                pl = next;
            }
            else {
                printf("NO\n");
                return;
            }
        }
    }
    printf("YES\n");
    return;
}

int main() {
    // ios::sync_with_stdio(false);
    // cin.tie(NULL), cout.tie(NULL);
    T = 1;
    ri(T); // delete if one test case
    for (int _ = 1; _ <= T; _++) {
        solve(_);
    }
    return 0;
}
### Prompt

Create a solution in CPP for the following problem:

Uh oh! Ray lost his array yet again! However, Omkar might be able to help because he thinks he has found the OmkArray of Ray's array. The OmkArray of an array a with elements a_1, a_2, …, a_{2k-1}, is the array b with elements b_1, b_2, …, b_{k} such that b_i is equal to the median of a_1, a_2, …, a_{2i-1} for all i. Omkar has found an array b of size n (1 ≤ n ≤ 2 ⋅ 10^5, -10^9 ≤ b_i ≤ 10^9). Given this array b, Ray wants to test Omkar's claim and see if b actually is an OmkArray of some array a. Can you help Ray?

The median of a set of numbers a_1, a_2, …, a_{2i-1} is the number c_{i} where c_{1}, c_{2}, …, c_{2i-1} represents a_1, a_2, …, a_{2i-1} sorted in nondecreasing order. 

Input

Each test contains multiple test cases. The first line contains a single integer t (1 ≤ t ≤ 10^4) — the number of test cases. Description of the test cases follows.

The first line of each test case contains an integer n (1 ≤ n ≤ 2 ⋅ 10^5) — the length of the array b.

The second line contains n integers b_1, b_2, …, b_n (-10^9 ≤ b_i ≤ 10^9) — the elements of b.

It is guaranteed the sum of n across all test cases does not exceed 2 ⋅ 10^5. 

Output

For each test case, output one line containing YES if there exists an array a such that b_i is the median of a_1, a_2, ..., a_{2i-1} for all i, and NO otherwise. The case of letters in YES and NO do not matter (so yEs and No will also be accepted).

Examples

Input


5
4
6 2 1 3
1
4
5
4 -8 5 6 -7
2
3 3
4
2 1 2 3


Output


NO
YES
NO
YES
YES


Input


5
8
-8 2 -6 -5 -4 3 3 2
7
1 1 3 1 0 -2 -1
7
6 12 8 6 2 6 10
6
5 1 2 3 6 7
5
1 3 4 3 0


Output


NO
YES
NO
NO
NO

Note

In the second case of the first sample, the array [4] will generate an OmkArray of [4], as the median of the first element is 4.

In the fourth case of the first sample, the array [3, 2, 5] will generate an OmkArray of [3, 3], as the median of 3 is 3 and the median of 2, 3, 5 is 3.

In the fifth case of the first sample, the array [2, 1, 0, 3, 4, 4, 3] will generate an OmkArray of [2, 1, 2, 3] as 

  * the median of 2 is 2 
  * the median of 0, 1, 2 is 1 
  * the median of 0, 1, 2, 3, 4 is 2 
  * and the median of 0, 1, 2, 3, 3, 4, 4 is 3. 



In the second case of the second sample, the array [1, 0, 4, 3, 5, -2, -2, -2, -4, -3, -4, -1, 5] will generate an OmkArray of [1, 1, 3, 1, 0, -2, -1], as 

  * the median of 1 is 1 
  * the median of 0, 1, 4 is 1 
  * the median of 0, 1, 3, 4, 5 is 3 
  * the median of -2, -2, 0, 1, 3, 4, 5 is 1 
  * the median of -4, -2, -2, -2, 0, 1, 3, 4, 5 is 0 
  * the median of -4, -4, -3, -2, -2, -2, 0, 1, 3, 4, 5 is -2 
  * and the median of -4, -4, -3, -2, -2, -2, -1, 0, 1, 3, 4, 5, 5 is -1 



For all cases where the answer is NO, it can be proven that it is impossible to find an array a such that b is the OmkArray of a.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define x first
#define y second
#define LL long long
#define LD long double
#define Complex complex<double>
#define y1 ___y1
#define next ___next
#define left ___left
#define right ___right
#define pii pair<int, int>
#define pll pair<LL, LL>
#define pdd pair<double, double>
#define pldld pair<LD, LD>
#define vi vector<int>
#define vl vector<LL>
#define vii vector<pii>
#define vll vector<pll>
#define PQ priority_queue
#define ffo fflush(stdout)
#define gch getchar()
#define e (int)(1e9 + 7)
#define e2 (double)2.71828182846
#define pi (double)3.14159265358979
#define ri(X) scanf("%d", &(X))
#define rii(X, Y) scanf("%d%d", &(X), &(Y))
#define riii(X, Y, Z) scanf("%d%d%d", &(X), &(Y), &(Z))
#define rl(X) scanf("%lld", &(X))
#define rll(X, Y) scanf("%lld%lld", &(X), &(Y))
#define rlll(X, Y, Z) scanf("%lld%lld%lld", &(X), &(Y), &(Z))
#define printi(X) printf("%d", (int)(X))
#define printii(X, Y) printf("%d %d", (int)(X), (int)(Y))
#define printiii(X, Y, Z) printf("%d %d %d", (int)(X), (int)(Y), (int)(Z))
#define printl(X) printf("%lld", (LL)(X))
#define printll(X, Y) printf("%lld %lld", (LL)(X), (LL)(Y))
#define printlll(X, Y, Z) printf("%lld %lld %lld", (LL)(X), (LL)(Y), (LL)(Z))
#define enter printf("\n")
#define space printf(" ")
struct matrix {
    int sz;
    LL a[105][105];
    matrix& operator = (const matrix &T) {
        sz = T.sz;
        for (int i = 1; i <= sz; i++) {
            for (int j = 1; j <= sz; j++) {
                a[i][j] = T.a[i][j];
            }
        }
        return *this;
    }
    matrix operator + (const matrix &T) const {
        matrix ans;
        ans.sz = sz;
        for (int i = 1; i <= sz; i++) {
            for (int j = 1; j <= sz; j++) {
                ans.a[i][j] = a[i][j] + T.a[i][j];
                ans.a[i][j] %= e;
            }
        }
        return ans;
    }
    matrix operator * (const matrix &T) const {
        matrix ans;
        ans.sz = sz;
        for (int i = 1; i <= sz; i++) {
            for (int j = 1; j <= sz; j++) {
                ans.a[i][j] = 0;
                for (int k = 1; k <= sz; k++) {
                    ans.a[i][j] += a[i][k] * T.a[k][j];
                    ans.a[i][j] %= e;
                }
            }
        }
        return ans;
    }
    matrix I() {
        matrix ans;
        ans.sz = sz;
        for (int i = 1; i <= sz; i++) {
            for (int j = 1; j <= sz; j++) {
                if (i == j) ans.a[i][j] = 1;
                else ans.a[i][j] = 0;
            }
        }
        return ans;
    }
    matrix power(LL p) {
        if (p == 0) return I();
        if (p == 1) return *this;
        matrix tmp = power(p / 2);
        if (p % 2) tmp = tmp * tmp * (*this);
        else tmp = tmp * tmp;
        return tmp;
    }
    void print() {
        for (int i = 1; i <= sz; i++) {
            for (int j = 1; j <= sz; j++) {
                printf(j == sz? "%lld\n" : "%lld ", a[i][j]);
            }
        }
        return;
    }
};
struct polynomial {
    vector<Complex> v;
    int sz;
    polynomial operator * (const polynomial &T) const {
        polynomial ans;
        if (sz >= T.sz) {
            ans = *this;
            for (int i = 0; i < T.sz; i++) {
                ans.v[i] *= T.v[i];
            }
        }
        else {
            ans = T;
            for (int i = 0; i < sz; i++) {
                ans.v[i] *= v[i];
            }
        }
        return ans;
    }
};
polynomial FFT(polynomial a) {
    if (a.sz <= 1) return a;
    polynomial even, odd;
    even.sz = odd.sz = 0;
    for (int i = 0; i < a.sz; i += 2) {
        even.v.pb(a.v[i]);
        even.sz++;
    }
    for (int i = 1; i < a.sz; i += 2) {
        odd.v.pb(a.v[i]);
        odd.sz++;
    }
    polynomial Even = FFT(even);
    polynomial Odd = FFT(odd);
    polynomial ans;
    ans.sz = a.sz;
    for (int i = 0; i < ans.sz; i++) {
        ans.v.pb(0);
    }
    for (int i = 0; i < a.sz / 2; i++) {
        Complex w = polar(1.0, -2 * pi * i / a.sz) * Odd.v[i];
        ans.v[i] = Even.v[i] + w;
        ans.v[i + a.sz / 2] = Even.v[i] - w;
    }
    return ans;
}
polynomial IFFT(polynomial a) {
    for (int i = 0; i < a.sz; i++) {
        a.v[i] = conj(a.v[i]);
    }
    polynomial ans = FFT(a);
    for (int i = 0; i < a.sz; i++) {
        ans.v[i] = conj(ans.v[i]);
        ans.v[i] /= ans.sz;
    }
    return ans;
}
struct polygon {
    int n;
    pii a[1005];
    double area() {
        double d1 = 0, d2 = 0;
        for (int i = 0; i < n; i++) {
            d1 += a[i].x * a[(i + 1) % n].y;
            d2 += a[(i + 1) % n].x * a[i].y;
        }
        return (d1 - d2) / 2;
    }
    bool inside(pldld p) {
        int ct = 0;
        LD d;
        pldld p1 = a[0];
        for (int i = 1; i <= n; i++) {
            pldld p2 = a[i % n];
            if (p.y > min(p1.y, p2.y) && p.y <= max(p1.y, p2.y) && p.x <= max(p1.x, p2.x) && p1.y != p2.y) {
                d = (p.y - p1.y) * (p2.x - p1.x) / (p2.y - p1.y) + p1.x;
                if (p1.x == p2.x || p.x <= d) ct++;
            }
            p1 = p2;
        }
        return ct % 2;
    }
};
struct segtree {
    int l, r, mid;
    LL val = 0, lazy = 0;
    segtree *lc, *rc;
    segtree(int L, int R) {
        l = L;
        r = R;
        mid = (l + r) / 2;
        if (l != r) {
            lc = new segtree(l, mid);
            rc = new segtree(mid + 1, r);
        }
    }
    void apply(LL X) {
        val += X;
        // val += X * (r - l + 1);
        lazy += X;
    }
    void push() {
        if (l == r) return;
        lc->apply(lazy);
        rc->apply(lazy);
        lazy = 0;
    }
    void update(int L, int R, LL X) {
        push();
        if (l == L && r == R) {
            apply(X);
            return;
        }
        else if (R <= mid) lc->update(L, R, X);
        else if (L >= mid + 1) rc->update(L, R, X);
        else {
            lc->update(L, mid, X);
            rc->update(mid + 1, R, X);
        }
        val = min(lc->val, rc->val);
        // val = lc->val + rc->val;
    }
    LL query(int L, int R) {
        push();
        if (l == L && r == R) return val;
        else if (R <= mid) return lc->query(L, R);
        else if (L >= mid + 1) return rc->query(L, R);
        else {
            return min(lc->query(L, mid), rc->query(mid + 1, R));
            // return lc->query(L, mid) + rc->query(mid + 1, R);
        }
    }
    //segroot = new segtree(0, n - 1)
} *segroot;
LL power(LL a, LL p) {
    if (p == 0) return 1;
    if (p == 1) return a;
    LL tmp = power(a, p / 2);
    if (p % 2) tmp = tmp * tmp % e * a;
    else tmp *= tmp;
    return tmp % e;
}
struct node {
    int num;
    int l, r;
};

int T;
int n, a[200005];
node p[200005];

void solve(int CASE) {
    ri(n);
    for (int i = 1; i <= n; i++) {
        ri(a[i]);
    }
    int small = 0;
    int big = 0;
    int sz = 3;
    p[3].l = 1;
    p[3].r = 2;
    p[3].num = a[1];
    int pl = 3;
    for (int i = 2; i <= n; i++) {
        if (a[i] == p[pl].num) {
        }
        else if (a[i] > p[pl].num) {
            if (p[pl].r == 2) {
                int next = ++sz;
                p[pl].r = next;
                p[next].num = a[i];
                p[next].l = pl;
                p[next].r = 2;
                pl = next;
            }
            else if (p[p[pl].r].num == a[i]) {
                pl = p[pl].r;
            }
            else if (p[p[pl].r].num > a[i]) {
                int next = ++sz;
                p[next].num = a[i];
                p[next].l = pl;
                p[next].r = p[pl].r;
                p[p[next].r].l = next;
                p[pl].r = next;
                pl = next;
            }
            else {
                printf("NO\n");
                return;
            }
        }
        else {
            if (p[pl].l == 1) {
                int next = ++sz;
                p[pl].l = next;
                p[next].num = a[i];
                p[next].l = 1;
                p[next].r = pl;
                pl = next;
            }
            else if (p[p[pl].l].num == a[i]) {
                pl = p[pl].l;
            }
            else if (p[p[pl].l].num < a[i]) {
                int next = ++sz;
                p[next].num = a[i];
                p[next].r = pl;
                p[next].l = p[pl].l;
                p[p[next].l].r = next;
                p[pl].l = next;
                pl = next;
            }
            else {
                printf("NO\n");
                return;
            }
        }
    }
    printf("YES\n");
    return;
}

int main() {
    // ios::sync_with_stdio(false);
    // cin.tie(NULL), cout.tie(NULL);
    T = 1;
    ri(T); // delete if one test case
    for (int _ = 1; _ <= T; _++) {
        solve(_);
    }
    return 0;
}
```