YouKn0wWho has an integer sequence a_1, a_2, … a_n. Now he will split the sequence a into one or more consecutive subarrays so that each element of a belongs to exactly one subarray. Let k be the number of resulting subarrays, and h_1, h_2, …, h_k be the lengths of the longest increasing subsequences of corresponding subarrays.

For example, if we split [2, 5, 3, 1, 4, 3, 2, 2, 5, 1] into [2, 5, 3, 1, 4], [3, 2, 2, 5], [1], then h = [3, 2, 1].

YouKn0wWho wonders if it is possible to split the sequence a in such a way that the [bitwise XOR](https://en.wikipedia.org/wiki/Bitwise_operation#XOR) of h_1, h_2, …, h_k is equal to 0. You have to tell whether it is possible.

The longest increasing subsequence (LIS) of a sequence b_1, b_2, …, b_m is the longest sequence of valid indices i_1, i_2, …, i_k such that i_1 < i_2 < … < i_k and b_{i_1} < b_{i_2} < … < b_{i_k}. For example, the LIS of [2, 5, 3, 3, 5] is [2, 3, 5], which has length 3.

An array c is a subarray of an array b if c can be obtained from b by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

Input

The first line contains a single integer t (1 ≤ t ≤ 10 000) — the number of test cases.

The first line of each test case contains a single integer n (2 ≤ n ≤ 10^5).

The second line of each test case contains n integers a_1, a_2, …, a_n (1 ≤ a_i ≤ 10^9).

It is guaranteed that the sum of n over all test cases doesn't exceed 3 ⋅ 10^5.

Output

For each test case, print "YES" (without quotes) if it is possible to split into subarrays in the desired way, print "NO" (without quotes) otherwise. You can print each letter in any register (upper or lower).

Example

Input


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


Output


YES
NO
YES
YES

Note

In the first test case, YouKn0wWho can split the sequence in the following way: [1, 3, 4], [2, 2], [1, 5]. This way, the LIS lengths are h = [3, 1, 2], and the bitwise XOR of the LIS lengths is 3 ⊕ 1 ⊕ 2 = 0.

In the second test case, it can be shown that it is impossible to split the sequence into subarrays that will satisfy the condition.
					/*
					ID: abdelra29
LANG: JAVA
PROG: zerosum
					*/
						/*
						TO LEARN
				
						2-euler tour
					
						*/
						/*
						TO SOLVE 
						codeforces 722 kavi on pairing duty
						*/
						/*
						bit manipulation shit
						1-Computer Systems: A Programmer's Perspective
						2-hacker's delight
						*/
						/*
						TO WATCH
						
						*/
						            import java.util.*;
								    import java.math.*;
								    import java.io.*; 
								    import java.util.stream.Collectors;

								       public class A{
						            static FastScanner scan=new FastScanner();
									     public static PrintWriter out = new PrintWriter (new BufferedOutputStream(System.out));
									     static boolean vis[][];
	
 static int CeilIndex(int A[], int l, int r, int key)
    {
        while (r - l > 1) {
            int m = l + (r - l) / 2;
            if (A[m] >= key)
                r = m;
            else
                l = m;
        }
 
        return r;
    }
    static int CeilIndex2(int A[], int l, int r, int key)
    {
        while (r - l > 1) {
            int m = l + (r - l) / 2;
            if (A[m] <= key)
                r = m;
            else
                l = m;
        }
 
        return r;
    }
 
   static void reverse(int a[], int n)
    {
        int[] b = new int[n];
        int j = n;
        for (int i = 0; i < n; i++) {
            b[j - 1] = a[i];
            j = j - 1;
        }
        for(int i=0;i<n;i++)
        	a[i]=b[i];
  
        
    }
  
 

				public static void main(String[] args)  throws Exception 
						      {
						

						 /*
						 very important tips 
						 1-just fucking think backwards once in your shitty life
						 2-consider brute forcing and finding some patterns and observations
						 3-when you're in contest don't get out because you think there is no enough time
						
						 */
						
							//scan=new FastScanner("binary.in");
								///out = new PrintWriter("zerosum.out");
								 
								 							 /*
								 READING 
							
								 3-Introduction to DP with Bitmasking codefoces
								 4-Bit Manipulation hackerearth
								 5-read more about mobious and inculsion-exclusion 
								 */
								 /*
								
								 */
								
					
								    int tt=1;
				
						


	tt=scan.nextInt();

								int T=1;
								 outer:while(tt-->0)
								    {
int n=scan.nextInt();
int A[]=new int[n];
for(int i=0;i<n;i++)
	A[i]=scan.nextInt();
if(n%2==0)
{
	out.println("YES");
	continue outer;
}
int tailTable2[]=new int[n];
        int[] tailTable = new int[n];
        int len; // always points empty slot
 int dp1[]=new int[n];
 int dp2[]=new int[n];
        tailTable[0] = A[0];
        len = 1;
        dp1[0]=1;
        for (int i = 1; i < n; i++) {
            if (A[i] < tailTable[0])
                // new smallest value
                tailTable[0] = A[i];
 
            else if (A[i] > tailTable[len - 1])
                // A[i] wants to extend largest subsequence
                tailTable[len++] = A[i];
 
            else
                // A[i] wants to be current end candidate of an existing
                // subsequence. It will replace ceil value in tailTable
                tailTable[CeilIndex(tailTable, -1, len - 1, A[i])] = A[i];
       dp1[i]=len;
        }
 reverse(A,n);
 tailTable2[0] = A[0];
        len = 1;
        for (int i = 1; i < n; i++) {
            if (A[i] > tailTable2[0])
                // new smallest value
                tailTable2[0] = A[i];
 
            else if (A[i] < tailTable2[len - 1])
                // A[i] wants to extend largest subsequence
                tailTable2[len++] = A[i];
 
            else
                // A[i] wants to be current end candidate of an existing
                // subsequence. It will replace ceil value in tailTable
                tailTable2[CeilIndex2(tailTable2, -1, len - 1, A[i])] = A[i];
        dp2[i]=len;
        }
        for(int i=0;i<n-1;i++)
        {
        	if((dp1[i]^dp2[n-i-2])==0)
        	{
        		//out.println(i+" "+dp1[i]+" "+dp2[n-i-2]);
        		out.println("YES");
        		continue outer;
        	}
        }
        out.println("NO");
 
     
	 }

								

		out.close();
					}
					
			


					static class special{
					boolean is;
					char c;
					public special(boolean is,char c)
					{
						this.is=is;
						this.c=c;
					}

						 @Override
								            public int hashCode() {
								                return (int)(c+ 31 *(is?1:0));
								            }
						  @Override
								            public boolean equals(Object o){
								            //	System.out.println("FUCK");
								                if (o == this) return true;
								                if (o.getClass() != getClass()) return false;
								                special t = (special)o;
								                return t.is == is && t.c == c;
								            }
					}
		
								   
								    
								  
								     static class FastScanner
						{
						    private int BS = 1 << 16;
						    private char NC = (char) 0;
						    private byte[] buf = new byte[BS];
						    private int bId = 0, size = 0;
						    private char c = NC;
						    private double cnt = 1;
						    private BufferedInputStream in;
						 
						    public FastScanner() {
						        in = new BufferedInputStream(System.in, BS);
						    }
						 
						    public FastScanner(String s) {
						        try {
						            in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
						        } catch (Exception e) {
						            in = new BufferedInputStream(System.in, BS);
						        }
						    }
						 
						    private char getChar() {
						        while (bId == size) {
						            try {
						                size = in.read(buf);
						            } catch (Exception e) {
						                return NC;
						            }
						            if (size == -1) return NC;
						            bId = 0;
						        }
						        return (char) buf[bId++];
						    }
						 
						    public int nextInt() {
						        return (int) nextLong();
						    }
						 
						    public int[] nextInts(int N) {
						        int[] res = new int[N];
						        for (int i = 0; i < N; i++) {
						            res[i] = (int) nextLong();
						        }
						        return res;
						    }
						 
						    public long[] nextLongs(int N) {
						        long[] res = new long[N];
						        for (int i = 0; i < N; i++) {
						            res[i] = nextLong();
						        }
						        return res;
						    }
						 
						    public long nextLong() {
						        cnt = 1;
						        boolean neg = false;
						        if (c == NC) c = getChar();
						        for (; (c < '0' || c > '9'); c = getChar()) {
						            if (c == '-') neg = true;
						        }
						        long res = 0;
						        for (; c >= '0' && c <= '9'; c = getChar()) {
						            res = (res << 3) + (res << 1) + c - '0';
						            cnt *= 10;
						        }
						        return neg ? -res : res;
						    }
						 
						    public double nextDouble() {
						        double cur = nextLong();
						        return c != '.' ? cur : cur + nextLong() / cnt;
						    }
						 
						    public double[] nextDoubles(int N) {
						        double[] res = new double[N];
						        for (int i = 0; i < N; i++) {
						            res[i] = nextDouble();
						        }
						        return res;
						    }
						 
						    public String next() {
						        StringBuilder res = new StringBuilder();
						        while (c <= 32) c = getChar();
						        while (c > 32) {
						            res.append(c);
						            c = getChar();
						        }
						        return res.toString();
						    }
						 
						    public String nextLine() {
						        StringBuilder res = new StringBuilder();
						        while (c <= 32) c = getChar();
						        while (c != '\n') {
						            res.append(c);
						            c = getChar();
						        }
						        return res.toString();
						    }
						 
						    public boolean hasNext() {
						        if (c > 32) return true;
						        while (true) {
						            c = getChar();
						            if (c == NC) return false;
						            else if (c > 32) return true;
						        }
						    }
						}

								     static class Pair implements Comparable<Pair>{
								            public long x, y,z;
								            public Pair(long x1, long y1,long z1) {
								                x=x1;
								                y=y1;
								                z=z1;
								            }
								             public Pair(long x1, long y1) {
								                x=x1;
								                y=y1;
								    
								            }
								            
								            @Override
								            public int hashCode() {
								                return (int)(x + 31 * y);
								            }
								            public String toString() {
								                return x + " " + y+" "+z;
								            }
								            @Override
								            public boolean equals(Object o){
								                if (o == this) return true;
								                if (o.getClass() != getClass()) return false;
								                Pair t = (Pair)o;
								                return t.x == x && t.y == y&&t.z==z;
								            }
								    public int compareTo(Pair o)
								    {
								  	
								return (int)(x-o.x);
								     
								        }
								     
								    }
								}

								
								    
								   

								     
