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. 
import java.util.*;
import java.lang.*;
import java.io.*;

public class Codeforces {
    static FastReader sc=new FastReader();
	static PrintWriter out=new PrintWriter(System.out);
	static long mod=1000000007;
	static long mod1=998244353;
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
		int t=I();
		while(t-->0)
		{
			int n=I();
			int a[]=new int[n];
			int b[]=new int[n];
			int sorted=0;
			for(int i=0;i<n;i++){
				a[i]=I();
				if(i!=0){
					if(a[i]>=a[i-1])sorted++;
				}
				b[i]=a[i];
			}
			if(sorted==n-1){out.println("YES");continue;}
			if(n==1){out.println("YES");continue;}
			sort(b);
			HashMap<Integer,pair> hm=new HashMap<>();
			for(int i=0;i<n;i++){
				if(hm.containsKey(b[i])){
					pair p=hm.get(b[i]);
					if(i%2==0)p.a++;
					else p.b++;
					hm.put(b[i],p);
				}else{
					pair p=new pair(0,0);
					if(i%2==0)p.a++;
					else p.b++;
					hm.put(b[i],p);
				}
			}
			int q=0;
			for(int i=0;i<n;i++){
				pair p=hm.get(a[i]);
				if(i%2==0){
					if(p.a>0){
						p.a--;
						hm.put(a[i],p);
					}
					else if(p.a==0){q=1;break;}
				}else{
					if(p.b>0){
						p.b--;
						hm.put(a[i],p);
					}
					else if(p.b==0){q=1;break;}
				}
			}
			if(q==1)out.println("NO");
			else out.println("YES");
		}
		out.close();
	}
	public static long kadane(long a[],int n)
	{
		long max_sum=Long.MIN_VALUE,max_end=0;
		for(int i=0;i<n;i++){
			max_end+=a[i];
			if(max_sum<max_end){max_sum=max_end;}
			if(max_end<0){max_end=0;}
		}
		return max_sum;
	}
	public static void DFS(ArrayList<Integer> arr[],int s,boolean visited[])
	{
		visited[s]=true;
		for(int i:arr[s]){
			if(!visited[i]){
				DFS(arr,i,visited);
			}
		}
	}
	public static int BS(long a[],long x,int ii,int jj)
	{
		// int n=a.length;
		int mid=0;
		int i=ii,j=jj;
		while(i<j)
		{
			mid=(i+j)/2;
			if(a[mid]>x)
			j=mid-1;
			else if(a[mid]<x)
			i=mid+1;
			else return mid;
		}
		if(a[i]>x)
		return i-1;
		return i;
	}
	public static ArrayList<Integer> prime(int n)
	{
	    ArrayList<Integer> arr=new ArrayList<>();
	    boolean prime[] = new boolean[n + 1];
        for (int i = 0; i <= n; i++)
        prime[i] = true;
        for (int p = 2; p * p <= n; p++)
        {
            if (prime[p] == true)
            {
                for (int i = p * p; i <= n; i += p)
                prime[i] = false;
            }
        }
        for (int i = 2; i <= n; i++)
        {
            if (prime[i] == true)
            arr.add(i);
        }
        return arr;
	}
	public static HashSet<Integer> primeSet(int n)
	{
	    HashSet<Integer> arr=new HashSet<>();
	    boolean prime[] = new boolean[n + 1];
        for (int i = 0; i <= n; i++)
        prime[i] = true;
        for (int p = 2; p * p <= n; p++)
        {
            if (prime[p] == true)
            {
                for (int i = p * p; i <= n; i += p)
                prime[i] = false;
            }
        }
        for (int i = 2; i <= n; i++)
        {
            if (prime[i] == true)
            arr.add(i);
        }
        return arr;
	}

	// Fenwick / BinaryIndexed  Tree  USE IT - FenwickTree ft1=new FenwickTree(n);
	public static class FenwickTree
	{
		long farr[];
		int n;
		public FenwickTree(int c)
		{
			n=c+1;
			farr=new long[n];
		}
		public void update_range(int l,int r,long p)
		{
			update(l,p);
			update(r+1,(-1)*p);
		}
		public void update(int x,long p)
		{
			for(;x<n;x+=x&(-x))
			{
				farr[x]+=p;
			}
		}
		public long get(int x)
		{
			long ans=0;
			for(;x>0;x-=x&(-x))
			{
				ans=ans+farr[x];
			}
			return ans;
		}
	}

	//Disjoint Set Union
	public static class DSU
	{
	    static int par[],rank[];
	    public DSU(int c)
	    {
	        par=new int[c+1];
	        rank=new int[c+1];
	        for(int i=0;i<=c;i++)
	        {
	            par[i]=i;
	            rank[i]=0;
	        }
	    }
	    public static int find(int a)
	    {
	        if(a==par[a])
	        return a;
	        return par[a]=find(par[a]);
	    }
	    public static void union(int a,int b)
	    {
	        int a_rep=find(a),b_rep=find(b);
	        if(a_rep==b_rep)
	        return;
	        if(rank[a_rep]<rank[b_rep])
	        par[a_rep]=b_rep;
	        else if(rank[a_rep]>rank[b_rep])
	        par[b_rep]=a_rep;
	        else
	        {
	            par[b_rep]=a_rep;
	            rank[a_rep]++;
	        }
	    }
	}

	//SEGMENT TREE CODE

	// public static void segmentUpdate(int si,int ss,int se,int qs,int qe,long x)
	// {
	// 	if(ss>qe || se<qs)return;
	// 	if(qs<=ss && qe>=se)
	// 	{
	// 		seg[si][0]+=1L;
	// 		seg[si][1]+=x*x;
	// 		seg[si][2]+=2*x;
	// 		return;
	// 	}
	// 	int mid=(ss+se)/2;
	// 	segmentUpdate(2*si+1,ss,mid,qs,qe,x);
	// 	segmentUpdate(2*si+2,mid+1,se,qs,qe,x);
	// }
	// public static long segmentGet(int si,int ss,int se,int x,long f,long s,long t,long a[])
	// {
	// 	if(ss==se && ss==x)
	// 	{
	// 		f+=seg[si][0];
	// 		s+=seg[si][1];
	// 		t+=seg[si][2];
	// 		long ans=a[x]+(f*((long)x+1L)*((long)x+1L))+s+(t*((long)x+1L));
	// 		return ans;
	// 	}
	// 	int mid=(ss+se)/2;
	// 	if(x>mid){
	// 		return segmentGet(2*si+2,mid+1,se,x,f+seg[si][0],s+seg[si][1],t+seg[si][2],a);
	// 	}else{
	// 		return segmentGet(2*si+1,ss,mid,x,f+seg[si][0],s+seg[si][1],t+seg[si][2],a);
	// 	}
	// }

	public static class pair
    {
    	int a;
    	int b;
    	public pair(int val,int index)
    	{
    	    a=val;
    	    b=index;
    	}
    }
	public static class myComp implements Comparator<pair>
	{
		//sort in ascending order.
		// public int compare(pair p1,pair p2)
		// {
		// 	if(p1.a==p2.a)
    	//     return 0;
    	//     else if(p1.a<p2.a)
    	//     return -1;
    	//     else
    	//     return 1;
		// }
		//sort in descending order.
		public int compare(pair p1,pair p2)
    	{
    	    if(p1.a==p2.a)
    	    return 0;
    	    else if(p1.a<p2.a)
    	    return 1;
    	    else
    	    return -1;
    	}
	}
    public static class myComp1 implements Comparator<pair1>
    {
		//sort in ascending order.
    	public int compare(pair1 p1,pair1 p2)
    	{
    	    if(p1.a==p2.a)
    	    return 0;
    	    else if(p1.a<p2.a)
    	    return -1;
    	    else
    	    return 1;
    	}
		//sort in descending order.
		// public int compare(pair p1,pair p2)
    	// {
    	//     if(p1.a==p2.a)
    	//     return 0;
    	//     else if(p1.a<p2.a)
    	//     return 1;
    	//     else
    	//     return -1;
    	// }
    }
	public static class pair1
    {
    	long a;
    	long b;
    	public pair1(long val,long index)
    	{
    	    a=val;
    	    b=index;
    	}
    }
    public static ArrayList<pair1> mergeIntervals(ArrayList<pair1> arr)
	{
	    //****************use this in main function-Collections.sort(arr,new myComp1());
	    ArrayList<pair1> a1=new ArrayList<>();
	    if(arr.size()<=1)
	    return arr;
	    a1.add(arr.get(0));
	    int i=1,j=0;
	    while(i<arr.size())
	    {
	        if(a1.get(j).b<arr.get(i).a)
	        {
	           a1.add(arr.get(i));
	           i++;
	           j++;
	        }
	        else if(a1.get(j).b>arr.get(i).a && a1.get(j).b>=arr.get(i).b)
	        {
	            i++;
	        }
	        else if(a1.get(j).b>=arr.get(i).a)
	        {
	            long a=a1.get(j).a;
	            long b=arr.get(i).b;
	            a1.remove(j);
	            a1.add(new pair1(a,b));
	            i++;
	        }
	    }
	    return a1;
	}
	public static boolean palindrome(String s,int n)
	{
		for(int i=0;i<=n/2;i++){
			if(s.charAt(i)!=s.charAt(n-i-1)){
				return false;
			}
		}
		return true;
	}
	public static long countDigit(long n)
	{
	    long sum=0;
	    while(n!=0)
	    {
	        sum++;
	        n=n/10;
	    }
	    return sum;
	}
	public static long digitSum(long n)
	{
	    long sum=0;
	    while(n!=0)
	    {
	        sum=sum+n%10;
	        n=n/10;
	    }
	    return sum;
	}
	public static long gcd(long a,long b)
	{
	    if(b==0)
	    return a;
	    else
	    return gcd(b,a%b);
	}
	public static int gcd(int a,int b)
	{
	    if(b==0)
	    return a;
	    else
	    return gcd(b,a%b);
	}
	public static void printArray(long a[])
	{
		for(int i=0;i<a.length;i++){
			out.print(a[i]+" ");
		}
		out.println();
	}
	public static void printArray(ArrayList<Long> arr)
	{
		for(int i=0;i<arr.size();i++){
			out.print(arr.get(i)+" ");
		}
		out.println();
	}
	public static long pwr(long m,long n)
	{
		long res=1;
		m=m%mod;
		if(m==0)
		return 0;
		while(n>0)
		{
			if((n&1)!=0)
			{
				res=(res*m)%mod;
			}
			n=n>>1;
			m=(m*m)%mod;
		}
		return res;
	}
	public static void sort(int[] A)
	{
        int n = A.length;
        Random rnd = new Random();
        for(int i=0; i<n; ++i)
		{
            int tmp = A[i];
            int randomPos = i + rnd.nextInt(n-i);
            A[i] = A[randomPos];
            A[randomPos] = tmp;
        }
        Arrays.sort(A);
    }
    public static void sort(long[] A)
	{
	    int n = A.length;
        Random rnd = new Random();
        for(int i=0; i<n; ++i)
		{
            long tmp = A[i];
            int randomPos = i + rnd.nextInt(n-i);
            A[i] = A[randomPos];
            A[randomPos] = tmp;
        }
	    Arrays.sort(A);
	}
	public static int I(){return sc.I();}
    public static long L(){return sc.L();}
    public static String S(){return sc.S();}
    public static double D(){return sc.D();}
}
class FastReader {  
    BufferedReader br;
    StringTokenizer st;
    public FastReader(){
        br = new BufferedReader(new InputStreamReader(System.in));
    }
    String next(){
        while (st == null || !st.hasMoreElements()){
            try {
                st = new StringTokenizer(br.readLine());
            }
            catch (IOException e){
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }
    int I(){ 
        return Integer.parseInt(next());
    }
    long L(){ 
        return Long.parseLong(next());
    }
    double D(){
         return Double.parseDouble(next());
    }
    String S(){
        String str = "";
        try 
        {
            str = br.readLine();
        }
        catch (IOException e)
        {
            e.printStackTrace();
        }
        return str;
    }
}
