[数据结构与算法]Odd Swap Sort

You are given an array?a1,a2,…,ana1,a2,…,an. You can perform operations on the array. In each operation you can choose an integer?ii?(1≤i<n1≤i<n), and swap elements?aiai?and?ai+1ai+1?of the array, if?ai+ai+1ai+ai+1?is odd.

Determine whether it can be sorted in non-decreasing order using this operation any number of times.

Input

Each test contains multiple test cases. The first line contains a single integer?tt?(1≤t≤1051≤t≤105)?— the number of test cases. Description of the test cases follows.

The first line of each test case contains a single integer?nn?(1≤n≤1051≤n≤105)?— the length of the array.

The second line of each test case contains?nn?integers?a1,a2,…,ana1,a2,…,an?(1≤ai≤1091≤ai≤109)?— the elements of the array.

It is guaranteed that the sum of?nn?over all test cases does not exceed?2?1052?105.

Output

For each test case, print?"Yes"?or?"No"?depending on whether you can or can not sort the given array.

You may print each letter in any case (for example,?"YES",?"Yes",?"yes",?"yEs"?will all be recognized as positive answer).

Example

input

Copy

4
4
1 6 31 14
2
4 2
5
2 9 6 7 10
3
6 6 6

output

Copy

Yes
No
No
Yes

Note

In the first test case, we can simply swap?3131?and?1414?(31+14=4531+14=45?which is odd) and obtain the non-decreasing array?[1,6,14,31][1,6,14,31].

In the second test case, the only way we could sort the array is by swapping?44?and?22, but this is impossible, since their sum?4+2=64+2=6?is even.

In the third test case, there is no way to make the array non-decreasing.

In the fourth test case, the array is already non-decreasing.

思路：这个题说要只有在奇与偶相邻时才能交换位置，那么我们可以将奇与偶分开存，整体排序看是否与原数组的位置发生改变，奇奇与偶偶不能不能改变，（而奇偶随便改就不用相邻奇偶的大小），如果排过序与原数组的顺序不一样说明是不对的，变不成。

完整代码：

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef vector<int> vi;
//#define int long long
#define fir first
#define sec second
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)x.size()
#define rep(i, l, r) for (int i = l; i <= r; ++i)
#define repd(i, l, r) for (int i = l; i >= r; --i)
#define pb push_back


const int N=1e5+10;

void solve()
{
    int n;
    cin>>n;
    vector<int>a;
    vector<int>b;
    vector<int>c;
    vector<int>d;
    int x;
    rep(i,1,n)
    {
        cin>>x;
        if(x&1)a.pb(x);
        else b.pb(x);
    }
    c=a;
    d=b;
    sort(c.begin(),c.end());
    sort(d.begin(),d.end());
    if(c==a&&d==b)cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin>>t;
    while(t--)
    {
        solve();
    }
    return 0;
}