#include<bits/stdc++.h>
#include<string>
using namespace std;


typedef long long ll;
typedef vector<ll> vi;
typedef vector<int> vin;
typedef vector<pair<ll, ll>> vll;
typedef vector<pair<int, int>> vii;
#define endl "\n"
#define pb push_back
#define fp(i,a,b) for(int i=a;i<b;++i)
#define fq(i,a,b) for(int i=a;i<=b;++i)
#define fst ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define all(a) a.begin(),a.end()
#define p11 cout<<"YES"<<endl
#define p00 cout<<"NO"<<endl
#define read(x) for(auto &i:x) cin>>i;
#define print(x) for(auto i:x) cout<<i<<" "; cout<<endl;
#define mod 1e9+7

// vector<bool> ppprinteersd(MAX+1,0);
// void soe()

void sol()
{

    ll n, m;
    cin >> n >> m;
    vi v(n);
    //read(v);

    unordered_map<ll, ll> mp;


    for (ll i = 0; i < n; ++i)
    {
        ll x; cin >> x;
        v[i] = x % m;
        mp[x % m]++;
    }

    ll cnt = 0;

// print(v);

    if (mp[0] > 0)cnt = 1;

    ll kk;
    if (m % 2 == 0)
        kk = m / 2;
    else
        kk = m / 2 - 1;
    //for(ll i=1;i<=(m+1)/2 && i<m;++i)
    for (ll i = 1; i <= kk; ++i)
    {

        //cout<<i<<" "<<cnt<<endl;
        if (i == m - i)
        {
            if (mp[i] != 0)
                cnt += 1;
            continue;
        }
        if ( mp[i] == 0 || mp[m - i] == 0)
        {
            if (mp[i] != 0)
            {
                cnt += ((i + m - 1) / m);
            } else
            {
                cnt += (((m - i) + m - 1) / m);
            }
            continue;
            cnt += (mp[i] + mp[m - i] + 1) / 2;
            mp[i] = mp[m - i] = 0;
            continue;
        }

        ll tmp = min(mp[i], mp[i - 1]);
        if (abs(mp[i] - mp[m - i]) == 1)tmp++;
        mp[i] = max(0ll, mp[i] - tmp - 1);
        mp[m - i] = max(0ll, mp[m - i] - tmp - 1);
        cnt += tmp + mp[i] + mp[m - i];


    }

    cout << cnt;




}


long long gcd(long long int a, long long int b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

long long lcm(int a, int b)
{
    return (a / gcd(a, b)) * b;
}
void fpar(int arr1[], int arr2[], int n,
          int m, int x)
{
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (arr1[i] + arr2[j] == x)
                cout << arr1[i] << " " << arr2[j] << endl;
}




int maxSubArraySum(vi a, int size)
{
    int max_so_far = INT_MIN, max_ending_here = 0;

    for (int i = 0; i < size; i++)
    {
        max_ending_here = max_ending_here + a[i];
        if (max_so_far < max_ending_here)
            max_so_far = max_ending_here;

        if (max_ending_here < 0)
            max_ending_here = 0;
    }
    return max_so_far;
}

int maxSum(vi arr, int n, int k)
{
    // k must be greater
    if (n < k)
    {
        cout << "value11initid";
        return -1;
    }

    int res = 0;
    for (int i = 0; i < k; i++)
        res += arr[i];


    int curr_sum = res;
    for (int i = k; i < n; i++)
    {
        curr_sum += arr[i] - arr[i - k];
        res = max(res, curr_sum);
    }

    return res;
}

void showpq(priority_queue<ll > gq)
{
    priority_queue<ll> g = gq;
    while (!g.empty()) {
        cout << '\t' << g.top();
        g.pop();
    }
    cout << '\n';
}

ll hel(string s, ll i, ll k)
{
    ll n = s.size();
    ll m = min(i + k - 1, n - 1);
    for (; m >= i; --m)
    {
        if (s[m] == '*')return m;
    }
    return -1;

}
void getit()
{
    ll dssfds;
    return;
}
ll dffdsf12sda;
int dsd12sdssdsds;
bool ffffds;
ll dfdffdqweoo;
void findNumbers(int arr[], int n)
{
    int num[n];
    int b_minus_a = arr[n - 1] - arr[1];

    // b is calculated here
    num[1] = (arr[0] + b_minus_a) / 2;

    // a is calculated here
    num[0] = arr[0] - num[1];


    for (int i = 1; i <= (n - 2); i++)
        num[i + 1] = arr[i] - num[0];

    cout << "Numbers are: ";
    for (int i = 0; i < n; i++)
        cout << num[i] << " ";
}

ll cl(ll x, ll y)
{
    return (x + y - 1) / y;
}

ll factorial(ll n)
{
    ll res = 1, i;
    for (i = 2; i <= n; i++)
        res  = (res * i) ;
    return res;
}


ll findlen(long long n)
{
    ll count = 0;
    while (n != 0)
    {
        n = n / 10;
        ++count;
    }
    return count;
}

int countdig(long long n)
{
    int count = 0;
    while (n != 0)
    {
        n = n / 10;
        ++count;
    }
    return count;
}

ll finggiiutesp(vector<ll> arr)
{
    ll n = (ll)arr.size();

    unordered_map<ll, ll> map;
    for (ll i = 0; i < n; i++)
        map[arr[i] - i]++;
    ll res = 0;
    for (auto x : map) {
        ll cnt = x.second;
        res += ((cnt * (cnt - 1)) / 2);
    }

    return res;
}


ll countunsetbits(ll n)
{
    ll count = 0;

    for (ll x = 1; x <= n; x = x << 1)
        if ((x & n) == 0)
            count++;

    return count;
}

ll fact(ll n);

ll nCr(ll n, ll r)
{
    return fact(n) / (fact(r) * fact(n - r));
}

// Returns factorial of n
ll fact(ll n)
{
    ll res = 1;
    for (ll i = 2; i <= n; i++)
        res = res * i;
    return res;
}

void modify(string& s)
{
    int n = s.size();

    int i = 0;
    while (i < n)
    {
        int j = i;
        while (s[i] != '?')
        {
            i++;
        }
        int ln = j - i + 1;

    }
}

void sol22()
{
    ll n;
    cin >> n;
    vi v(n);
    read(v);

    set<ll> s;
    s.insert(-1e15);
    s.insert(1e15);
    s.insert(v[0]);

    for (ll i = 1; i < n; ++i)
    {
        if (v[i] == v[i - 1])
        {
            continue;
        }
        else if (v[i] < v[i - 1])
        {
            // shift median to lower value
            s.insert(v[i]);
            if ( (*s.upper_bound(v[i])) != v[i - 1])
            {
                cout << "NO"; return;
            }
        }
        else {
            // shift to median to higher value
            s.insert(v[i]);
            if ( (*s.upper_bound(v[i - 1])) != v[i])
            {
                cout << "NO"; return;
            }
        }
    }
    cout << "YES";



}




int main() {

    fst;
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    getit();
    getit();

    ll t = 1;
    cin >> t;

    for (ll ppp = 1; ppp <= t; ++ppp)
    {
        // cout<<"Case "<<i<<": ";
        getit();
        bool cdwnur443333;
        sol22();
        cout << endl;
    }

    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>
#include<string>
using namespace std;


typedef long long ll;
typedef vector<ll> vi;
typedef vector<int> vin;
typedef vector<pair<ll, ll>> vll;
typedef vector<pair<int, int>> vii;
#define endl "\n"
#define pb push_back
#define fp(i,a,b) for(int i=a;i<b;++i)
#define fq(i,a,b) for(int i=a;i<=b;++i)
#define fst ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define all(a) a.begin(),a.end()
#define p11 cout<<"YES"<<endl
#define p00 cout<<"NO"<<endl
#define read(x) for(auto &i:x) cin>>i;
#define print(x) for(auto i:x) cout<<i<<" "; cout<<endl;
#define mod 1e9+7

// vector<bool> ppprinteersd(MAX+1,0);
// void soe()

void sol()
{

    ll n, m;
    cin >> n >> m;
    vi v(n);
    //read(v);

    unordered_map<ll, ll> mp;


    for (ll i = 0; i < n; ++i)
    {
        ll x; cin >> x;
        v[i] = x % m;
        mp[x % m]++;
    }

    ll cnt = 0;

// print(v);

    if (mp[0] > 0)cnt = 1;

    ll kk;
    if (m % 2 == 0)
        kk = m / 2;
    else
        kk = m / 2 - 1;
    //for(ll i=1;i<=(m+1)/2 && i<m;++i)
    for (ll i = 1; i <= kk; ++i)
    {

        //cout<<i<<" "<<cnt<<endl;
        if (i == m - i)
        {
            if (mp[i] != 0)
                cnt += 1;
            continue;
        }
        if ( mp[i] == 0 || mp[m - i] == 0)
        {
            if (mp[i] != 0)
            {
                cnt += ((i + m - 1) / m);
            } else
            {
                cnt += (((m - i) + m - 1) / m);
            }
            continue;
            cnt += (mp[i] + mp[m - i] + 1) / 2;
            mp[i] = mp[m - i] = 0;
            continue;
        }

        ll tmp = min(mp[i], mp[i - 1]);
        if (abs(mp[i] - mp[m - i]) == 1)tmp++;
        mp[i] = max(0ll, mp[i] - tmp - 1);
        mp[m - i] = max(0ll, mp[m - i] - tmp - 1);
        cnt += tmp + mp[i] + mp[m - i];


    }

    cout << cnt;




}


long long gcd(long long int a, long long int b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

long long lcm(int a, int b)
{
    return (a / gcd(a, b)) * b;
}
void fpar(int arr1[], int arr2[], int n,
          int m, int x)
{
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (arr1[i] + arr2[j] == x)
                cout << arr1[i] << " " << arr2[j] << endl;
}




int maxSubArraySum(vi a, int size)
{
    int max_so_far = INT_MIN, max_ending_here = 0;

    for (int i = 0; i < size; i++)
    {
        max_ending_here = max_ending_here + a[i];
        if (max_so_far < max_ending_here)
            max_so_far = max_ending_here;

        if (max_ending_here < 0)
            max_ending_here = 0;
    }
    return max_so_far;
}

int maxSum(vi arr, int n, int k)
{
    // k must be greater
    if (n < k)
    {
        cout << "value11initid";
        return -1;
    }

    int res = 0;
    for (int i = 0; i < k; i++)
        res += arr[i];


    int curr_sum = res;
    for (int i = k; i < n; i++)
    {
        curr_sum += arr[i] - arr[i - k];
        res = max(res, curr_sum);
    }

    return res;
}

void showpq(priority_queue<ll > gq)
{
    priority_queue<ll> g = gq;
    while (!g.empty()) {
        cout << '\t' << g.top();
        g.pop();
    }
    cout << '\n';
}

ll hel(string s, ll i, ll k)
{
    ll n = s.size();
    ll m = min(i + k - 1, n - 1);
    for (; m >= i; --m)
    {
        if (s[m] == '*')return m;
    }
    return -1;

}
void getit()
{
    ll dssfds;
    return;
}
ll dffdsf12sda;
int dsd12sdssdsds;
bool ffffds;
ll dfdffdqweoo;
void findNumbers(int arr[], int n)
{
    int num[n];
    int b_minus_a = arr[n - 1] - arr[1];

    // b is calculated here
    num[1] = (arr[0] + b_minus_a) / 2;

    // a is calculated here
    num[0] = arr[0] - num[1];


    for (int i = 1; i <= (n - 2); i++)
        num[i + 1] = arr[i] - num[0];

    cout << "Numbers are: ";
    for (int i = 0; i < n; i++)
        cout << num[i] << " ";
}

ll cl(ll x, ll y)
{
    return (x + y - 1) / y;
}

ll factorial(ll n)
{
    ll res = 1, i;
    for (i = 2; i <= n; i++)
        res  = (res * i) ;
    return res;
}


ll findlen(long long n)
{
    ll count = 0;
    while (n != 0)
    {
        n = n / 10;
        ++count;
    }
    return count;
}

int countdig(long long n)
{
    int count = 0;
    while (n != 0)
    {
        n = n / 10;
        ++count;
    }
    return count;
}

ll finggiiutesp(vector<ll> arr)
{
    ll n = (ll)arr.size();

    unordered_map<ll, ll> map;
    for (ll i = 0; i < n; i++)
        map[arr[i] - i]++;
    ll res = 0;
    for (auto x : map) {
        ll cnt = x.second;
        res += ((cnt * (cnt - 1)) / 2);
    }

    return res;
}


ll countunsetbits(ll n)
{
    ll count = 0;

    for (ll x = 1; x <= n; x = x << 1)
        if ((x & n) == 0)
            count++;

    return count;
}

ll fact(ll n);

ll nCr(ll n, ll r)
{
    return fact(n) / (fact(r) * fact(n - r));
}

// Returns factorial of n
ll fact(ll n)
{
    ll res = 1;
    for (ll i = 2; i <= n; i++)
        res = res * i;
    return res;
}

void modify(string& s)
{
    int n = s.size();

    int i = 0;
    while (i < n)
    {
        int j = i;
        while (s[i] != '?')
        {
            i++;
        }
        int ln = j - i + 1;

    }
}

void sol22()
{
    ll n;
    cin >> n;
    vi v(n);
    read(v);

    set<ll> s;
    s.insert(-1e15);
    s.insert(1e15);
    s.insert(v[0]);

    for (ll i = 1; i < n; ++i)
    {
        if (v[i] == v[i - 1])
        {
            continue;
        }
        else if (v[i] < v[i - 1])
        {
            // shift median to lower value
            s.insert(v[i]);
            if ( (*s.upper_bound(v[i])) != v[i - 1])
            {
                cout << "NO"; return;
            }
        }
        else {
            // shift to median to higher value
            s.insert(v[i]);
            if ( (*s.upper_bound(v[i - 1])) != v[i])
            {
                cout << "NO"; return;
            }
        }
    }
    cout << "YES";



}




int main() {

    fst;
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    getit();
    getit();

    ll t = 1;
    cin >> t;

    for (ll ppp = 1; ppp <= t; ++ppp)
    {
        // cout<<"Case "<<i<<": ";
        getit();
        bool cdwnur443333;
        sol22();
        cout << endl;
    }

    return 0;
}

```