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.
//package Codeforces;
import java.util.*;

import java.io.*;
public  class template{
	
	static class FastScanner {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer("");
		String next () {
			while(!st.hasMoreTokens()) {
				try {
					st=new StringTokenizer(br.readLine());
				}catch(IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		
		int nextInt() {
			return Integer.parseInt(next());
		}
		
		int[] readArray(int n) {
			int a[] = new int[n];
			for(int i=0;i<n;i++) {
				a[i] = nextInt();
			}
			return a;
		}
		
		long nextLong() {
			return Long.parseLong(next());
		}
	}
	
	static class helper{
		
		//reverse 1-d Array
		public static void reverse(int arr[]) {
			int i = 0;
			int j = arr.length - 1;
			while(i<j) {
				int temp = arr[i];
				arr[i] = arr[j];
				arr[j] = temp;
			}
		}
		
		//gcd of two numbers
		public static int gcd(int a,int b) {
			if(b == 0) {
				return a;
			}
			return gcd(b,a%b);
		}
		
		//calculate ncr
		public static int ncr(int n,int r) {
			int num = n;
			int deno = r;
			int a1 = 1;
			int a2 = 1;
			for(int i=0;i<r;i++) {
				a1 *= num;
				a2 *= deno;
				num--;
				deno--;
			}
			int ans = a1/a2;
			return ans;
		}
		
		//isPalindrome
		public static boolean isPalindrome(String substring){
		    char ch[] = substring.toCharArray();
		    int i = 0;
		    int j = ch.length-1;
		    while(i<j){
		        char temp = ch[i];
		        ch[i] = ch[j];
		        ch[j] = temp;
		        i++;
		        j--;
		    }
		    String rev = String.valueOf(ch);
		    if(rev.equals(substring)){
		        return true;
		    }
		    else{
		        return false;
		    }
		}
		
		//isPowerOfTwo
		public static boolean isPowerOfTwo(long x)
	    {
	        /* First x in the below expression is
	        for the case when x is 0 */
	        return x != 0 && ((x & (x - 1)) == 0);
	    }
		
		//nextPowerOfTwo
		public static long nextPowerOfTwo(long n)
	    {
	        n--;
	        n |= n >> 1;
	        n |= n >> 2;
	        n |= n >> 4;
	        n |= n >> 8;
	        n |= n >> 16;
	        n++;
	         
	        return n;
	    }
	}
	

	
	public static void main(String[] args) {
		  FastScanner sc = new FastScanner();
		  PrintWriter out = new PrintWriter(System.out);
		  helper help = new helper();
		  long test = sc.nextLong();
		  while(test-->0) {
			  int n = sc.nextInt();
			  int arr[] = sc.readArray(n);
			  if(n%2 == 0) {
				  out.println("YES");
			  }
			  else {
				  boolean flag = false;
				  for(int i=0;i<arr.length-1;i++) {
					  if(arr[i] >= arr[i+1]) {
						  flag = true;
						  break;
					  }
				  }
				  if(flag) {
					  out.println("YES");
				  }
				  else {
					  out.println("NO");
				  }
			  }
		  }
		  out.flush();
	}
	
}

class pair {
	int value;
	int index;
	pair(int value,int index){
		this.value = value;
		this.index = index;
	}
	public int getValue() {
		return value;
	}
	public void setValue(int value) {
		this.value = value;
	}
	public int getIndex() {
		return index;
	}
	public void setIndex(int index) {
		this.index = index;
	}
}
