AquaMoon has n friends. They stand in a row from left to right, and the i-th friend from the left wears a T-shirt with a number a_i written on it. Each friend has a direction (left or right). In the beginning, the direction of each friend is right.

AquaMoon can make some operations on friends. On each operation, AquaMoon can choose two adjacent friends and swap their positions. After each operation, the direction of both chosen friends will also be flipped: left to right and vice versa.

AquaMoon hopes that after some operations, the numbers written on the T-shirt of n friends in the row, read from left to right, become non-decreasing. Also she wants, that all friends will have a direction of right at the end. Please find if it is possible.

Input

The input consists of multiple test cases. The first line contains a single integer t (1 ≤ t ≤ 50) — the number of test cases.

The first line of each test case contains a single integer n (1 ≤ n ≤ 10^5) — the number of Aquamoon's friends.

The second line contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 10^5) — the numbers, written on the T-shirts.

It is guaranteed that the sum of n for all test cases does not exceed 10^5.

Output

For each test case, if there exists a possible sequence of operations, print "YES" (without quotes); otherwise, print "NO" (without quotes).

You can print each letter in any case (upper or lower).

Example

Input


3
4
4 3 2 5
4
3 3 2 2
5
1 2 3 5 4


Output


YES
YES
NO

Note

The possible list of operations in the first test case:

  1. Swap a_1 and a_2. The resulting sequence is 3, 4, 2, 5. The directions are: left, left, right, right. 
  2. Swap a_2 and a_3. The resulting sequence is 3, 2, 4, 5. The directions are: left, left, right, right. 
  3. Swap a_1 and a_2. The resulting sequence is 2, 3, 4, 5. The directions are: right, right, right, right. 
#include<bits/stdc++.h>
#define ll long long int
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define inf (1<<30)
#define linf 1e18
#define ninf -1e9
#define loop(i,r) for(int i = 0; i < (r) ; i++)
#define loop1(i,r) for(int i=1;i<=r;i++)
#define looplr(i,l,r) for(int i=l;i<=r;i++)
#define rloop(i,r) for(int i=r;i>=0;i--)
#define min3(x1, x2, x3) (x3 > min(x1, x2) ? min(x2, x1) : x3)
#define max3(x1, x2, x3) (x3 < max(x1, x2) ? max(x1, x2) : x3)
#define sz(a) int((a).size())
#define vi vector< int >
#define vl vector<long long int>
#define vpi vector<pair<int, int> >
#define vpl vector<pair<long long int, long long int> >
#define pb push_back
#define umi unordered_map<int , int>
#define umc unordered_map<char , int>
#define uml unordered_map<long long int , long long int>
#define mpi map<int, int>
#define mpl map<ll, ll>
#define sti set<int>
#define stl set<long long int>
#define ff first
#define ss second
#define len(x) (int)x.length()
#define ctn continue
#define brk break
#define ub(i,x) upper_bound(i.begin(), i.end(),x)
#define lb(i,x) lower_bound(i.begin(), i.end(),x)
#define ump unordered_map
#define str string
#define pll pair<long long int, long long int>
#define pii pair<int, int>
#define memn1(x) memset(x,-1,sizeof(x))
#define mem1(x) memset(x,1,sizeof(x))
#define mem0(x) memset(x,0,sizeof(x))
#define rtn return
#define srt(x) sort(all(x))
#define srtgi(x) sort(all(x), greater<int>())
#define srtgl(x) sort(all(x), greater<ll>())
#define srtgpi(x) sort(all(x), greater<pii>())
#define srtgpl(x) sort(all(x), greater<pll>())
#define rsz resize
#define ins insert
#define ft front()
#define bk back()
#define nline cout<< "\n"
#define chngl "\n"
#define takei(input) scanf("%d",&input)
#define takel(input) scanf("%lld",&input)
#define takepl(input1,input2) scanf("%lld %lld",&input1, &input2)
#define takepi(input1, input2) scanf("%d %d",&input1, &input2)
#define PI (acos(-1))
#define mxpqi priority_queue<int>
#define mnpqi priority_queue<int, vector<int>, greater<int>>
#define mxpql priority_queue<ll>
#define mnpql priority_queue<ll, vector<ll>, greater<ll>>
#define putyes printf("Yes\n")
#define putno printf("No\n")

const int  mod = 1e9 + 7;
int dx[] = {0, 0, 1, -1};
int dy[] = { -1, 1, 0, 0};

using namespace std;
// #include<boost/multiprecision/cpp_int.hpp>
// using namespace boost::multiprecision;
//cpp_int

int getDigit ( int num ) {
	unsigned digit = 0 ;
	while ( num != 0 ) {
		num /= 10 ;
		digit ++;
	}
	return digit ;
}

ll Fact ( ll k ) {
	ll sum = 1 ;
	for ( ll i = 1 ; i <= k ; ++ i )
	{
		sum *= i ;
	}
	return sum ;
}
bool prime_checker(ll x) {
	for (ll i = 2; i * i <= x; i++) {
		if (x % i == 0) rtn false;
	}
	rtn true;
}
// Prime factor decomposition ex: {{2, 2}, {5, 1}, {101, 1}}
map<ll, ll> prime_fact(ll N) {
	map<ll, ll> res;
	for (ll a = 2; a * a <= N; ++a) {
		if (N % a != 0) continue;
		ll ex = 0 ; // exponent
		// Keep splitting as long as it breaks
		while (N % a == 0) {
			++ex;
			N /= a;
		}
		// push the result
		res[a] = ex;
	}
	// About the last remaining number
	if (N != 1) res[N] = 1;
	return res;
}

ll modPow(long long a, long long n,  long p) {
	if ( n == 0 ) return 1 ; // When supporting 0th power
	if (n == 1) return a % p;
	if (n % 2 == 1) return (a * modPow(a, n - 1, p)) % p;
	long long t = modPow(a, n / 2, p);
	return (t * t) % p;
}
//----------------------P&C-------------------------------------
ll f [ 2000001 ], rf [ 2000001 ];
ll inv (ll x) {
	ll res = 1 ;
	ll k = mod - 2 ;
	ll y = x;
	while (k) {
		if (k & 1 ) res = (res * y) % mod;
		y = (y * y) % mod;
		k /= 2 ;
	}
	return res;
}

ll C ( int n, int k) {
	if (k == 0 || n == k) rtn 1;
	if (k < 0 || n < k) return  0 ;
	////Init
	f [ 0 ] = 1 ;
	loop1 (i, n ) f [i] = (f [i - 1 ] * i) % mod;
	rf [ n - 1 ] = inv (f [ n - 1 ]);
	rloop (i, n - 2) rf [i] = (rf [i + 1 ] * (i + 1 )) % mod;
	/////end

	ll a = f [n]; // = n!
	ll b = rf [n - k]; // = (n-k)!
	ll c = rf [k]; // = k!

	ll bc = (b * c) % mod;

	return (a * bc) % mod;
}
ll P ( int n, int k) {
	if (k < 0 || n < k) return  0 ;

	ll a = f [n]; // = n!
	ll b = rf [n - k]; // = (n-k)!
	return (a * b) % mod;
}
ll H ( int n, int k) {
	if (n == 0 && k == 0 ) return  1 ;
	return C (n + k - 1 , k);
}
//----------------------------P&C-------------------------------------------

//-----------------runLengthEncoding--------------------------------
vector<pair<char, int>> RLE(string s) {
	int n = s.length();

	vector<pair<char, int>> res;
	char pre = s[0];
	int cnt = 1;
	for (int i = 1; i < n; i++) {
		if (pre != s[i]) {
			res.push_back({ s[i - 1], cnt });
			pre = s[i];
			cnt = 1;
		}
		else cnt++;
	}

	res.push_back({ pre, cnt });
	//for (auto &i : res) cout << i.ss << ' ' << i.ff << endl;
	return res;
}
//------------------------------------------------------------------

const int NN = 1e6 + 5;
int Prime[NN];
vector<int> prime;
void calPrime() {
	for (int i = 1; i <= 1000000; i++) Prime[i] = 1;
	for (int i = 2; i * i <= 1e6 + 1; i++) {
		if (Prime[i] == -1) ctn;
		Prime[i] = 1;
		prime.pb(i);
		for (int j = 2 * i; j <= 1e6 + 1; j +=  i) {
			Prime[j] = -1;
		}
	}

}
//----------------------max & min--------------------------------
template<class T> inline bool chmin(T& a, T b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}
template<class T> inline bool chmax(T& a, T b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}
//----------------------DSU------------------------------------------
int getparent(int a, vi &parent) {
	if (parent[a] == a) return a;
	return parent[a] = getparent(parent[a], parent);
}
void Union(int a, int b, vi &parent, vi &rank) {
	int pa = getparent(a, parent);
	int pb = getparent(b, parent);
	if (rank[pa] == rank[pb]) rank[pa]++;
	if (rank[pa] >= rank[pb]) {
		parent[pb] = pa;
	} else {
		parent[pa] = pb;
	}
}

//---------------------Count number of prime fact------------------
ll cntprime(int x)
{
	int res = 0, i;
	for (i = 2; i * i <= x; i++)
	{
		while (x % i == 0)
		{
			x /= i;
			res++;
		}
	}
	if (x > 1) res++;
	return res;
}

//-------------------------SPF-----------------------------------------
#define MAXN   1000001
int spf[MAXN];

void sieve()
{
	spf[1] = 1;
	for (int i = 2; i < MAXN; i++) spf[i] = i;
	for (int i = 4; i < MAXN; i += 2) spf[i] = 2;

	for (int i = 3; i * i < MAXN; i++)
	{
		if (spf[i] == i)
		{
			for (int j = i * i; j < MAXN; j += i)
				if (spf[j] == j)
					spf[j] = i;
		}
	}
}

// A O(log n) function returning primefactorization
// by dividing by smallest prime factor at every step
vector<int> getFactorization(int x)
{
	vector<int> ret;
	while (x != 1)
	{
		ret.push_back(spf[x]);
		x = x / spf[x];
	}
	return ret;
}
//---------------------------------------------------------------------------
//int getDigit ( int num )
// ll Fact ( ll k ) O(k)
// vector<pair<ll, ll> > prime_fact(ll N)
//bool prime_checker(x)
//ll cntprime(ll x)
//ll modPow(ll a, ll n,  ll p)


void solve() {
	int n ; cin >> n;
	map<ll, vl>ffmp, ssmp;
	vl a(n);
	
	loop(i, n )
	{
		cin >> a[i];
		ffmp[a[i]].pb(i + 1);
	}
	sort(all(a));
	loop(i, n )
	{
		ssmp[a[i]].pb(i + 1);
	}
	int ans = 0;
	auto myit = ssmp.begin();

	for (auto itr : ffmp)
	{
		ll xx = 0, yy = 0, ff = 0, zz = 0;
		vl vec = itr.ss;
		vl vvec = myit->ss;
		loop(i, vec.size())
		{
			if (vec[i] % 2 == 1) xx++;
			else yy++;
		}
		loop(i, vvec.size())
		{
			if (vvec[i] % 2 == 1) ff++;
			else zz++;
		}
		if (xx != ff || yy != zz) { ans = 1; break; }
		myit++;
	}
	if (ans == 1) {
		cout << "NO" << chngl;
	}
	else {
		cout << "YES" << chngl;
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	//calPrime();
	int tme = 1;
	cin >> tme;
	//int i = 1;
	while (tme--) {
		//cout << "Case #" << i << ": ";
		solve();

		//i++;
	}
	return 0;
}