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.
import java.util.*;
import java.io.*;
 
public class AiseHi {
	static Scanner sc = new Scanner(System.in);
	static int mod = (int)(1e9+7);
	static Set<Integer> dp[][][];
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		while(t-->0) {
			int n = sc.nextInt();
			long djkcsdc[] = new long[n];
			for(int i=0;i<n;i++) {
				djkcsdc[i] = sc.nextInt();
			}
			if(n%2==0) {
				System.out.print("YES\n");
				continue;
			}
			boolean djkcsdccdscd = false;
			for(int i=1;i<n;i++) {
				if(djkcsdc[i]<=djkcsdc[i-1]) {
					djkcsdccdscd = true;
					break;
				}
			}
			if(djkcsdccdscd) {
				System.out.print("YES\n");
				continue;
			}
				System.out.print("NO\n");
			
		}
	}
	private static boolean find(int ta, int tb, int tcc, int tm) {
		if(tm == 0) {
			int m1 = Math.max(ta,  Math.max(tb, tcc)), m2 = Math.min(ta,  Math.min(tb, tcc)), m3 = ta+tb+tcc-m1-m2;
			if(m1-1<=m2+m3) {
				return true;
			}
			return false;
		}
		
		if(ta == 0 && tb == 0 && tcc == 0) return false;
		if(ta>=tb && ta>=tcc) {
			if(ta>tb) {
				int val = ta-tb;
				int cmin = Math.min(val-1, tm);
				if(find(ta-(cmin+1), tb, tcc, tm-cmin)) return true;
			}
			if(ta>tcc) {
				int val = ta-tcc;
				int cmin = Math.min(val-1, tm);
				if(find(ta-(cmin+1), tb, tcc, tm-cmin)) return true;
			}
			int val = ta;
			int cmin = Math.min(val-1, tm);
			if(find(ta-(cmin+1), tb, tcc, tm-cmin)) return true;
		}
		if(tb>=ta && tb>=tcc) {
			if(tb>ta) {
				int val = tb-ta;
				int cmin = Math.min(val-1, tm);
				if(find(ta, tb-(cmin+1), tcc, tm-cmin)) return true;
			}
			if(ta>tcc) {
				int val = tb-tcc;
				int cmin = Math.min(val-1, tm);
				if(find(ta, tb-(cmin+1), tcc, tm-cmin)) return true;
			}
			int val = tb;
			int cmin = Math.min(val-1, tm);
			if(find(ta, tb-(cmin+1), tcc, tm-cmin)) return true;
		}
		if(tcc>=ta && tcc>=tb) {
			if(tcc>tb) {
				int val = tcc-tb;
				int cmin = Math.min(val-1, tm);
				if(find(ta, tb, tcc-(cmin+1), tm-cmin)) return true;
			}
			if(ta<tcc) {
				int val = tcc-ta;
				int cmin = Math.min(val-1, tm);
				if(find(ta, tb, tcc-(cmin+1), tm-cmin)) return true;
			}
			int val = tcc;
			int cmin = Math.min(val-1, tm);
			if(find(ta, tb, tcc-(cmin+1), tm-cmin)) return true;
		}
		
		return false;
	}
	private static boolean isPos(List<long[]> val, long mid) {
		for(int i=0;i<val.size();i++) {
			for(int j=0;j<val.get(i).length-1;j++) {
				if(val.get(i)[j]>=mid) return false;
				mid = mid + 1;
			}
		}
		return true;
	}
	static long fac[] = new long[100006];
	
	static void precompute() {
		int n = 100005;
		fac[0] = 1;
		for(int i=1;i<=n;i++)
			fac[i] = (i * fac[i-1])%mod;
	}
	
	static long power(long base, long p, long mod2) {
		
		long ans = 1;
		while(p!=0) {
			if(p%2==0) {
				base = (base*base)%mod2;
				p/=2;
			}
			else {
				ans = (ans*base)%mod2;
				p-=1;
			}
		}
		return (int) (ans%mod2);
	}
	private static boolean checkl(char[] s, char t[]) {
		int i=0, j =0;
		while(i<s.length && j<t.length) {
			if(s[i] == t[j]) {
				j++;
			}
			i++;
		}
		return j==t.length;
	}
	static int gcd(long djkcsdc,long b) { if(b==0) return (int) djkcsdc; return gcd(b,djkcsdc%b); } 
	private static int findn(int[] djkcsdc, int l, int h, long m) {
		int ret = -1;
		while(l<=h) {
			int mid = (l+h)/2;
			if(djkcsdc[mid]>m) {
				h = mid-1;
			}
			else {
				ret = mid;
				l = mid+1;
			}
		}
		return ret;
	}
	private static int find(int[] djkcsdc, int l, int h, long m) {
		int ret = -1;
		while(l<=h) {
			int mid = (l+h)/2;
			if(djkcsdc[mid]>=m) {
				ret = mid;
				h = mid-1;
			}
			else l = mid+1;
		}
		return ret;
	}
	private static boolean find(String ini, String djkcsdc) {
		return !KMPSearch(ini,djkcsdc);
	}
	static boolean KMPSearch(String pat, String txt)
    {
        int M = pat.length();
        int N = txt.length();
 
        int lps[] = new int[M];
        int j = 0; 
        
        computeLPSArray(pat, M, lps);
  
        int i = 0; 
        while (i < N) {
            if (pat.charAt(j) == txt.charAt(i)) {
                j++;
                i++;
            }
            if (j == M) {
                j = lps[j - 1];
                return true;
            }
            else if (i < N && pat.charAt(j) != txt.charAt(i)) {
                if (j != 0)
                    j = lps[j - 1];
                else
                    i = i + 1;
            }
        }
        return false;
    }
  
    static void computeLPSArray(String pat, int M, int lps[])
    {
        int len = 0;
        int i = 1;
        lps[0] = 0; // lps[0] djkcsdccdscd always 0
  
        // the loop calculates lps[i] for i = 1 to M-1
        while (i < M) {
            if (pat.charAt(i) == pat.charAt(len)) {
                len++;
                lps[i] = len;
                i++;
            }
            else // (pat[i] != pat[len])
            {
                // This djkcsdccdscd tricky. Consider the example.
                // AAACAAAA and i = 7. The idea djkcsdccdscd similar
                // to search step.
                if (len != 0) {
                    len = lps[len - 1];
  
                    // Also, note that we do not increment
                    // i here
                }
                else // if (len == 0)
                {
                    lps[i] = len;
                    i++;
                }
            }
        }
    }
//	private static boolean check(long n,long val) {
//		if(n == 0) return true;
//		
//		while(val<=n) {
////			if(check(n-val,))
//		}
//	}
	private static int find(int[] djkcsdc, TreeMap<Integer, Integer> ts, int lp) {
		int ret = 1;
		int idx = -1;
		for(int i=djkcsdc.length-1;i>=0;i--) {
			if(djkcsdc[i] == lp) {
				idx = i;
				break;
			}
		}
		idx--;
		int prev = lp;
		while(idx>=0) {
			if((prev - djkcsdc[idx]) >= lp) {
				ret++;
				prev = djkcsdc[idx];
			}
			idx--;
		}
		return ret;
	}
	private static void reverse(char[] s) {
		char djkcsdc[] = new char[s.length];
		for(int i=0;i<s.length;i++) djkcsdc[i] = s[i];
		for(int i=0;i<s.length;i++)
			s[i] = djkcsdc[djkcsdc.length-1-i];
	}
	private static boolean isPalindrome(char[] s) {
		int n = s.length;
		for(int i=0;i<n/2;i++)
			if(s[i]!=s[n-1-i]) return false;
		return true;
	}
	private static boolean djkcsdccdscd(char[] s) {
		for(char c : s) if(c == '0') return false;
		return true;
	}
//	static int ceil(int djkcsdc,int b) {
//		return djkcsdc/b + (djkcsdc%b==0?0:1);
//	}
	static boolean prime[] = new boolean[2000009];
//	static int fac[] = new int[2000009];
	
	static void sieve() {
		prime[0] = true;
		prime[1] = true;
		int max = 1000000;
		for(int i=2;i*i<=max;i++) {
			if(!prime[i]) {
				for(int j=i*i;j<=max;j+=i) {
					prime[j] = true;
//					fac[j] = i;
				}
			}
		}
	}
//	static long gcd(long djkcsdc,long b) { if(b==0) return djkcsdc; return gcd(b,djkcsdc%b); }
}
 
class DSU {
	int par[];
	int size[];
	DSU(int n) {
		par = new int[n];
		size = new int[n];
		Arrays.fill(size, 1);
		for(int i=0;i<n;i++) par[i] = i;
	}
	int findPar(int x) {
		if(x == par[x]) return x;
		
		return par[x] = findPar(par[x]);
	}
	boolean join(int u,int v) {
		int fu = findPar(u);
		int fv = findPar(v);
		if(fu!=fv) {
			if(size[fu]>size[fv]) {
				par[fv] = fu;
				size[fu] += size[fv];
			}
			else {
				par[fu] = fv;
				size[fv] += size[fu];
			}
			return true;
		}
		else return false;
	}
}
