#include <bits/stdc++.h>
using namespace std;
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define int long long
#define endl "\n"
#define pb push_back
#define ff first
#define ss second
#define sz(w) ((int)(w).size())
#define all(w) (w).begin(), (w).end()

using ll = long long;
using pii = pair<int, int>;

const double EPS = 1e-9;
const long long INF = 1e18;

template <typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << "(" << p.first << ", " << p.second << ")"; } 
template <typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for(const T &x : v) os << sep << x, sep = ", "; return os << '}'; }

template <typename T> void debug_out(string s, T t) { cout << "[" << s << ": " << t << "]\n"; }
template <typename T, typename... U> void debug_out(string s, T t, U... u) { int w = 0, c = 0; while(w < (int)s.size()) { if(s[w] == '(') c++; if(s[w] == ')') c--; if(!c and s[w] == ',') break; w++; } cout << "[" << s.substr(0, w) << ": " << t << "] "; debug_out(s.substr(w+2, (int)s.size()-w-1), u...); } 

#define DEBUG

#ifdef DEBUG
#define dbg(Z...) debug_out(#Z, Z)
#else
#define dbg(Z...) 
#endif

const int N = 1e6+5; // Change according to the question
// Reset the global variables(if any) 

void solve()
{
    int n; cin>>n;
    vector<int> b(n);
    for(int &x: b)
        cin>>x;
    int cur=b[0];
    vector<int> L, R;
    for(int i=1;i<n;i++)
    {
        // dbg(cur, L, R, b[i]);
        if(b[i]>cur)
        {
            L.pb(cur);
            if(sz(R))
            {
                if(R.back()<b[i])
                    {cout<<"NO"; return;}
                else if(R.back()==b[i])
                    R.pop_back();
            }

        }
        if(b[i]<cur)
        {
            R.pb(cur);
            if(sz(L))
            {
                if(L.back()>b[i])
                    {cout<<"NO"; return;}
                else if(L.back()==b[i])
                    L.pop_back();
            }   
        }
        cur=b[i];
    }
    cout<<"YES";
}

int32_t main()
{
    IOS;
    int T; cin >> T;
    for(int tc = 1; tc <= T; tc++)
    {
        // cout << "Case #" << tc << ": ";
        solve(); cout << endl;
    }
    return 0;
}
### Prompt

Please provide a cpp coded solution to the problem described below:

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 IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define int long long
#define endl "\n"
#define pb push_back
#define ff first
#define ss second
#define sz(w) ((int)(w).size())
#define all(w) (w).begin(), (w).end()

using ll = long long;
using pii = pair<int, int>;

const double EPS = 1e-9;
const long long INF = 1e18;

template <typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << "(" << p.first << ", " << p.second << ")"; } 
template <typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for(const T &x : v) os << sep << x, sep = ", "; return os << '}'; }

template <typename T> void debug_out(string s, T t) { cout << "[" << s << ": " << t << "]\n"; }
template <typename T, typename... U> void debug_out(string s, T t, U... u) { int w = 0, c = 0; while(w < (int)s.size()) { if(s[w] == '(') c++; if(s[w] == ')') c--; if(!c and s[w] == ',') break; w++; } cout << "[" << s.substr(0, w) << ": " << t << "] "; debug_out(s.substr(w+2, (int)s.size()-w-1), u...); } 

#define DEBUG

#ifdef DEBUG
#define dbg(Z...) debug_out(#Z, Z)
#else
#define dbg(Z...) 
#endif

const int N = 1e6+5; // Change according to the question
// Reset the global variables(if any) 

void solve()
{
    int n; cin>>n;
    vector<int> b(n);
    for(int &x: b)
        cin>>x;
    int cur=b[0];
    vector<int> L, R;
    for(int i=1;i<n;i++)
    {
        // dbg(cur, L, R, b[i]);
        if(b[i]>cur)
        {
            L.pb(cur);
            if(sz(R))
            {
                if(R.back()<b[i])
                    {cout<<"NO"; return;}
                else if(R.back()==b[i])
                    R.pop_back();
            }

        }
        if(b[i]<cur)
        {
            R.pb(cur);
            if(sz(L))
            {
                if(L.back()>b[i])
                    {cout<<"NO"; return;}
                else if(L.back()==b[i])
                    L.pop_back();
            }   
        }
        cur=b[i];
    }
    cout<<"YES";
}

int32_t main()
{
    IOS;
    int T; cin >> T;
    for(int tc = 1; tc <= T; tc++)
    {
        // cout << "Case #" << tc << ": ";
        solve(); cout << endl;
    }
    return 0;
}
```