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. 
// package codeforce.cf732;

import java.io.PrintWriter;
import java.util.*;

//https://codeforces.com/contest/1546/problem/C
/*
*
* */
public class C {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        PrintWriter pw = new PrintWriter(System.out);
        int t = sc.nextInt();
//        int t = 1;
        for (int i = 0; i < t; i++) {
            solve(sc, pw);
        }
        pw.close();
    }

    static void solve(Scanner in, PrintWriter out){
        int n = in.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }
        int[] seen = new int[(int) 1e5 + 1];
        LinkedList<Integer>[] ls = new LinkedList[seen.length];
        for (int i = 0; i < ls.length; i++) {
            ls[i] = new LinkedList<>();
        }
        int[] ans = new int[n];
        SegTree sg = new SegTree(seen.length + 2);
        for (int i = 0; i < n; i++) {
            int x = arr[i];
            ans[i] += sg.query(x + 1, seen.length);
            sg.modify(x, 1);
        }
        sg = new SegTree(seen.length + 2);
        for (int i = n - 1; i >= 0; i--) {
            ans[i] += sg.query(0, arr[i]);
            sg.modify(arr[i], 1);
        }

        for (int i = 0; i < n; i++) {
            int x = arr[i], val = ans[i];
            if (ls[x].size() == 0){
                ls[x].add(val);
            }else{
                if ((ls[x].getLast() + val) % 2 == 0){
                    ls[x].removeLast();
                }else{
                    ls[x].add(val);
                }
            }
        }
        for(LinkedList<Integer> ok : ls){
//            out.println(ok);
            if (ok.size() > 0){
                if (ok.size() == 1){
                    if (ok.peek() % 2 == 0){
//                        out.println("YES");
                    }else{
                        out.println("NO");
                        return;
                    }
                }else{
                    out.println("NO");
                    return;
                }
            }
        }
        out.println("YES");
    }

    static class SegTree {
        private int N;

        // Let UNIQUE be a value which does NOT
        // and will not appear in the segment tree
        private long UNIQUE = 0;

        // Segment tree values
        private long[] tree;

        public SegTree(int size) {
            tree = new long[2 * (N = size)];
            java.util.Arrays.fill(tree, UNIQUE);
        }

        public SegTree(long[] values) {
            this(values.length);
            for (int i = 0; i < N; i++) modify(i, values[i]);
        }

        // This is the segment tree function we are using for queries.
        // The function must be an associative function, meaning
        // the following property must hold: f(f(a,b),c) = f(a,f(b,c)).
        // Common associative functions used with segment trees
        // include: min, max, sum, product, GCD, and etc...
        private long function(long a, long b) {
            if (a == UNIQUE) return b;
            else if (b == UNIQUE) return a;

            return a + b; // sum over a range
            //return (a > b) ? a : b; // maximum value over a range
            //return (a < b) ? a : b; // minimum value over a range
            // return a * b; // product over a range (watch out for overflow!)
        }

        // Adjust point i by a value, O(log(n))
        public void modify(int i, long value) {
            tree[i + N] = function(tree[i + N], value);
//            tree[i + N] = value;

            for (i += N; i > 1; i >>= 1) {
                tree[i >> 1] = function(tree[i], tree[i ^ 1]);
            }

        }

        // Query interval [l, r), O(log(n)) ----> notice the exclusion of r
        public long query(int l, int r) {
            long res = UNIQUE;
            for (l += N, r += N; l < r; l >>= 1, r >>= 1) {
                if ((l & 1) != 0) res = function(res, tree[l++]);
                if ((r & 1) != 0) res = function(res, tree[--r]);
            }
            if (res == UNIQUE) {
                //throw new IllegalStateException("UNIQUE should not be the return value.");
                return 0;
            }
            return res;
        }


    }


    // Use this instead of Arrays.sort() on an array of ints. Arrays.sort() is n^2
    // worst case since it uses a version of quicksort. Although this would never
    // actually show up in the real world, in codeforces, people can hack, so
    // this is needed.
    static void ruffleSort(int[] a) {
        //ruffle
        int n=a.length;
        Random r=new Random();
        for (int i=0; i<a.length; i++) {
            int oi=r.nextInt(n), temp=a[i];
            a[i]=a[oi];
            a[oi]=temp;
        }

        //then sort
        Arrays.sort(a);
    }

}
