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.io.BufferedInputStream;
import java.io.Closeable;
import java.io.IOException;
import java.io.InputStream;

import java.util.Arrays;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Random;

public class P1546C {

    private static boolean solve(int n, int[] A) {
        final int[] C = new int[2*n];
        final Map<Integer, Integer> idx = new HashMap<>();
        for (int i = 0; i < n; i++) {
            final int j = idx.computeIfAbsent(A[i], a -> idx.size() * 2);
            C[j + i%2]++;
        }
        sort(A);
        for (int i = 0; i < n; i++) {
            final int j = idx.get(A[i]);
            if (C[j + i%2]-- <= 0) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) throws IOException {
        try {
            final FastReader fr = new FastReader(
                new BufferedInputStream(System.in));
            final StringBuilder sb = new StringBuilder();
            for (int t = fr.readInt(); t > 0; t--) {
                final int n = fr.readInt();
                final int[] A = fr.readInts(n);
                if (solve(n, A)) {
                    sb.append("YES\n");
                } else {
                    sb.append("NO\n");
                }
            }
            System.out.print(sb);
        } catch (Throwable t) {
            t.printStackTrace(System.out);
            System.exit(1);
        }
    }

    private static final void log(Object o) {
        System.err.println(o);
    }

    private static final void log(String format, Object... args) {
        System.err.println(String.format(null, format, args));
    }

    private static class FastReader implements Closeable {
        private static final byte B_SP = ' ';
        private static final byte B_CR = '\r';
        private static final byte B_LF = '\n';
        private static final byte B_0 = '0';
        private static final byte B_9 = '9';
        private static final byte B_DASH = '-';

        private final InputStream in;
        private byte prev;

        public FastReader(InputStream in) {
            this.in = in;
        }

        public byte read() throws IOException {
            return (prev = (byte) in.read());
        }

        public byte readNonWs() throws IOException {
            byte b;
            do {
                b = read();
            } while (b <= B_SP);
            return b;
        }

        public int readInt() throws IOException {
            byte b = readNonWs();
            final boolean neg = (b == B_DASH);
            if (neg) {
                b = read();
            }
            int i = (b - B_0);
            b = read();
            while (b >= B_0 && b <= B_9) {
                i = i * 10 + (b - B_0);
                b = read();
            }
            return neg ? -i : i;
        }

        public int[] readInts(int n) throws IOException  {
            final int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = readInt();
            }
            return arr;
        }

        public int[][] readInts(int n, int m) throws IOException {
            final int[][] arr = new int[n][m];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    arr[i][j] = readInt();
                }
            }
            return arr;
        }

        public long readLong() throws IOException {
            byte b = readNonWs();
            final boolean neg = (b == B_DASH);
            if (neg) {
                b = read();
            }
            long i = (b - B_0);
            b = read();
            while (b >= B_0 && b <= B_9) {
                i = i * 10 + (b - B_0);
                b = read();
            }
            return neg ? -i : i;
        }

        public long[] readLongs(int n) throws IOException  {
            final long[] arr = new long[n];
            for (int i = 0; i < n; i++) {
                arr[i] = readLong();
            }
            return arr;
        }

        public long[][] readLongs(int n, int m) throws IOException  {
            final long[][] arr = new long[n][m];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    arr[i][j] = readLong();
                }
            }
            return arr;
        }

        public int readToken(byte[] tbuf) throws IOException {
            byte b = readNonWs();
            int i = 0;
            do {
                tbuf[i++] = b;
                b = read();
            } while (b >= B_SP);
            return i;
        }

        public int readLine(byte[] lbuf) throws IOException {
            byte b;
            if (prev == B_CR) {
                b = read();
                if (b == B_LF) {
                    b = read();
                }
            } else {
                b = read();
            }
            int i = 0;
            while (b >= B_SP) {
                lbuf[i++] = b;
                b = read();
            }
            return i;
        }

        @Override
        public void close() throws IOException {
            in.close();
        }
    }

    private static int[] toIntArray(final List<Integer> lst) {
        final int[] arr = new int[lst.size()];
        int i = 0;
        for (final int x : lst) {
            arr[i++] = x;
        }
        return arr;
    }

    private static long[] toLongArray(final List<Long> lst) {
        final long[] arr = new long[lst.size()];
        int i = 0;
        for (final long x : lst) {
            arr[i++] = x;
        }
        return arr;
    }

    private static int[][] getDarts(final int n, final int m,
                                    final int[][] E) {
        final List<List<Integer>> darts = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            darts.add(new ArrayList<>());
        }
        for (int j = 0; j < m; j++) {
            final int u = E[j][0];
            final int v = E[j][1];
            darts.get(u).add(v);
            darts.get(v).add(u);
        }
        final int[][] D = new int[n][];
        int i = 0;
        for (final List<Integer> lst : darts) {
            D[i++] = toIntArray(lst);
        }
        return D;
    }

    private static final Random rng = new Random();

    private static void shuffle(int[] arr, int lo, int hi) {
        int k = hi - lo;
        for (int i = hi-1; i > lo; i--) {
            int j = lo + rng.nextInt(k--);
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
    }

    private static void sort(int[] arr) {
        shuffle(arr, 0, arr.length);
        Arrays.sort(arr);
    }
}
