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 javafx.scene.layout.Priority;
import sun.reflect.generics.tree.Tree;

import java.awt.*;
import java.sql.Array;
import java.util.*;
import java.io.*;
import java.util.stream.Stream;

import static java.lang.Math.*;
public class C
{
    static InputReader in=new InputReader(System.in);
    static OutputWriter out=new OutputWriter(System.out);
    static StringBuilder sb=new StringBuilder();
    static long MOD = (long)(998244353);

    // Main Class Starts Here
    public static void main(String args[])throws IOException
    {
        // Write your code.
        int t = in();
        while(t-->0) {
            int n = in();
            int ar[] = an(n);
            int a[][] = new int[100001][2];
            for(int i = 0; i < n; i++){
                a[ar[i]][i % 2]++;
            }

            Arrays.sort(ar);
            for(int i = 0; i < n; i++){
                a[ar[i]][i % 2]--;
            }

            boolean isPossible = true;
            for(int i = 0;i < n; i++){
                if(a[ar[i]][0] != 0 || a[ar[i]][1] != 0) {
                    isPossible = false;
                    break;
                }
            }
            if(isPossible) app("YES\n");
            else app("NO\n");
        }
        out.printLine(sb);
        out.close();
    }

    static class Pair{

        int index;
        int height;

        public Pair(int index, int height){
            this.index = index;
            this.height = height;
        }

        public String toString(){
            return "[ "+index+" , "+height+" ]";
        }
    }

    static class DisjointSet{
        int par[];
        int rank[];
        int n;
        public DisjointSet(int n){
            this.n = n;
            par = new int[n];
            rank = new int[n];
            for(int i = 0; i < n; i++){
                par[i] = i;
            }
        }

        public int findPar(int i){
            // path compression.
            if(par[i] != i){
                par[i] = findPar(par[i]);
            }
            return par[i];
        }

        public int merge(int x, int y){
            int parX = findPar(x);
            int parY = findPar(y);
            if(parX == parY) return 0; // no decrease in connected components
            if(rank[parX] > rank[parY]){
                // merge y to x.
                par[parY] = parX;
            }
            else if(rank[parY] > rank[parX]){
                par[parX] = parY;
            }
            else{
                par[parY] = parX;
                rank[parX]++;
            }
            return 1; // after merging the decrease in connected components is 1.
        }
    }

    public static class Edge{
        int from;
        int to;
        int id;
        boolean visited;
        public Edge(int from, int to, int id){
            this.from = from;
            this.to = to;
            this.id =id;
            this.visited = false;
        }
    }

    public static int[] an(int n) {
        int ar[]=new int[n];
        for(int i=0;i<n;i++)
            ar[i]=in();
        return ar;
    }

    public static long[] lan(int n) {
        long ar[]=new long[n];
        for(int i=0;i<n;i++)
            ar[i]=lin();
        return ar;
    }

    public static String atos(Object ar[]) {
        return Arrays.toString(ar);
    }

    public static int in() {
        return in.readInt();
    }

    public static long lin() {
        return in.readLong();
    }

    public static String sn() {
        return in.readString();
    }

    public static void prln(Object o) {
        out.printLine(o);
    }

    public static void prn(Object o) {
        out.print(o);
    }

    public static void display(int a[]) {
        out.printLine(Arrays.toString(a));
    }

    public static HashMap<Integer,Integer> hm(int a[]){
        HashMap<Integer,Integer> map=new HashMap<>();
        for(int i=0; i < a.length;i++) {
            int keep = (int)map.getOrDefault(a[i],0);
            map.put(a[i],++keep);
        }
        return map;
    }

    public static void app(Object o) {
        sb.append(o);
    }

    public static long calcManhattanDist(int x1,int y1,int x2,int y2) {
        long xa = Math.abs(x1-x2);
        long ya = Math.abs(y1-y2);
        return (xa+ya);
    }


    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1)
                throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public int readInt() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public long readLong() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public String readString() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        public boolean isSpaceChar(int c) {
            if (filter != null)
                return filter.isSpaceChar(c);
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public String next() {
            return readString();
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);
        }
    }

    static class OutputWriter {
        private final PrintWriter writer;

        public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }

        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }

        public void print(Object...objects) {
            for (int i = 0; i < objects.length; i++) {
                if (i != 0)
                    writer.print(' ');
                writer.print(objects[i]);
            }
        }

        public void printLine(Object...objects) {
            print(objects);
            writer.println();
        }

        public void close() {
            writer.close();
        }
    }
}