description: 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.
solution: import java.io.*;
  import java.util.Arrays;
  import java.util.*;
  import java.util.Scanner;
  import java.util.StringTokenizer;
  
  
  
  
  public class copy {
  
  
      public static boolean checker(long[] arr, long K, long diff) {
          long collect = 0;
          for (int i = 0; i < arr.length; i++) {
              if (arr[i] > diff)
                  collect += arr[i] - diff;
          }
  
          if (collect >= K)
              return true;
          else
              return false;
      }
  
      public static long search(long[] arr, long K, long R) {
          long l = 0;
          long r = R;
  
          while (l <= r) {
              long mid = (l + r) / 2;
  
              if (checker(arr, K, mid)) {
                  if (checker(arr, K, mid + 1))
                      l = mid + 1;
                  else
                      return mid;
              } else
                  r = mid - 1;
          }
          return -1;
      }
  
      static void sieveOfEratosthenes(int n, ArrayList<Integer> arr, ArrayList<Integer> arr1) {
          // Create a boolean array
          // "prime[0..n]" and
          // initialize all entries
          // it as true. A value in
          // prime[i] will finally be
          // false if i is Not a
          // prime, else true.
          boolean prime[] = new boolean[n + 1];
          for (int i = 0; i <= n; i++)
              prime[i] = true;
  
          for (int p = 2; p * p <= n; p++) {
              // If prime[p] is not changed, then it is a
              // prime
              if (prime[p] == true) {
  
                  // Update all multiples of p
                  for (int i = p * p; i <= n; i += p)
                      prime[i] = false;
              }
          }
  
          // Print all prime numbers
          int x = 0;
          for (int i = 2; i <= n; i++) {
              if (prime[i] == true) {
  
                  arr.add(i);
  
  
              }
  
          }
          System.out.println(arr.size());
      }
  
      public static boolean check(String s, int K, char ch) {
          ArrayList<Integer> arr = new ArrayList<>();
          for (int i = 0; i < s.length(); i++) {
              if (s.charAt(i) == ch)
                  arr.add(i);
          }
  //        if(K==1 && ch=='z')
  //            System.out.println(arr);
          if (arr.size() == 0)
              return false;
          if (arr.get(0) >= K)
              return false;
          if (s.length() - 1 - arr.get(arr.size() - 1) >= K)
              return false;
          for (int i = 1; i < arr.size(); i++) {
              if (arr.get(i) - arr.get(i - 1) > K)
                  return false;
          }
          return true;
      }
  
      public static int check(long N) {
          int sum = 0;
          while (N > 0) {
              sum += N % 10;
              N = N / 10;
          }
          return sum;
  
      }
  
      public static long call(long N) {
          long l = 1;
          long r = (long) Math.floor(Math.sqrt(N));
          while (l <= r) {
              long mid = (l + r) / 2;
              double left = N / (double) (mid) - mid;
              int right = check(mid);
              System.out.println(mid + " " + left + " " + right);
              if (mid == 10)
                  System.out.println(left + " " + right);
              if (left > right)
                  l = mid + 1;
              else if (right > left)
                  r = mid - 1;
              else
                  return mid;
          }
          return -1;
      }
  
      public static int path(ArrayList<ArrayList<Integer>> arr, int X, int parent, int[] gold, PriorityQueue<Integer> pq) {
          int max = 0;
          ArrayList<Integer> ch = new ArrayList<>();
          for (int i : arr.get(X)) {
              if (i != parent) {
                  ch.add(path(arr, i, X, gold, pq));
              }
          }
          Collections.sort(ch, Collections.reverseOrder());
          for (int i = 1; i < ch.size(); i++)
              pq.add(ch.get(i));
  
  
          if (ch.size() == 0)
              return gold[X];
          else
              return ch.get(0) + gold[X];
  
      }
  
      public static long fac(long N, long mod) {
          if (N == 0)
              return 1;
          if(N==1)
              return 1;
          return ((N % mod) * (fac(N - 1, mod) % mod)) % mod;
      }
  
      public static String form(char ch, int freq) {
          String s = "";
          for (int i = 1; i <= freq; i++)
              s += ch;
          return s;
      }
  
      static long power(long x, long y, long p) {
  
          // Initialize result
          long res = 1;
  
          // Update x if it is more than or
          // equal to p
          x = x % p;
  
          while (y > 0) {
  
              // If y is odd, multiply x
              // with result
              if (y % 2 == 1)
                  res = (res * x) % p;
  
              // y must be even now
              y = y >> 1; // y = y/2
              x = (x * x) % p;
          }
  
          return res;
      }
  
      // Returns n^(-1) mod p
      static long modInverse(long n, long p) {
          return power(n, p - 2, p);
      }
  
      // Returns nCr % p using Fermat's
      // little theorem.
      static long nCrModPFermat(long n, long r,
                                long p) {
  
          if (n < r)
              return 0;
          // Base case
          if (r == 0)
              return 1;
  
          // Fill factorial array so that we
          // can find all factorial of r, n
          // and n-r
  
  
  //        System.out.println(modInverse(fac(r,p),p));
  //        System.out.println(modInverse(fac(n-r,p),p));
          return ((fac(n, p) % p * (modInverse(fac(r, p), p)
                  % p)) % p * (modInverse(fac(n - r, p), p)
                  % p)) % p;
      }
  
      public static boolean check(long[] arr, long time, int M) {
          long sum = 0;
          int count = 0;
          for (int i = 0; i < arr.length; i++) {
              sum += arr[i];
              if (sum >= time) {
                  ++count;
                  sum = 0;
              }
          }
  
          if (sum >= time)
              ++count;
  
          return count >= M;
      }
  
      public static int check(ArrayList<Integer> arr, ArrayList<Integer> arr2) {
          int l = 0, r = 0, ans = 0;
          while (l < arr.size() && r < arr2.size()) {
              if (arr.get(l) < arr2.get(r))
                  ++l;
              else if (arr.get(l) > arr2.get(r))
                  ++r;
              else {
                  ++ans;
                  ++l;
                  ++r;
              }
          }
          return ans;
      }
  
  
      public static int find(int[] parent, int x) {
          if (parent[x] == x)
              return x;
          return find(parent, parent[x]);
      }
  
      public static void merge(int[] parent, int[] rank, int x, int y) {
          int x1 = find(parent, x);
          int y1 = find(parent, y);
          if (rank[x1] > rank[y1]) {
              parent[y1] = x1;
  
          } else if (rank[y1] > rank[x1]) {
              parent[x1] = y1;
          } else {
              parent[y1] = x1;
              rank[x1]++;
          }
      }
  
      public static int check(ArrayList<ArrayList<Integer>> arr, int e1, int e2, int N) {
          boolean[] visited = new boolean[N];
          visited[0] = true;
          int[] dist = new int[N];
          Queue<Integer> queue = new LinkedList<>();
          queue.add(0);
          Arrays.fill(dist, -1);
          dist[0] = 0;
          while (queue.size() > 0) {
              int x = queue.poll();
              for (int i : arr.get(x)) {
                  if (!visited[i] || (e1 == x && e2 == i)) {
                      System.out.println(x + " " + dist[x]);
                      dist[i] = dist[x] + 1;
                      visited[i] = true;
                      queue.add(i);
                  }
              }
  
          }
  
  
          return dist[N - 1];
      }
  
      static int N;
  
      static void rotate90Clockwise(String a[][]) {
  
          // Traverse each cycle
          for (int i = 0; i < N / 2; i++) {
              for (int j = i; j < N - i - 1; j++) {
  
                  // Swap elements of each cycle
                  // in clockwise direction
                  String temp = a[i][j];
                  a[i][j] = a[N - 1 - j][i];
                  a[N - 1 - j][i] = a[N - 1 - i][N - 1 - j];
                  a[N - 1 - i][N - 1 - j] = a[j][N - 1 - i];
                  a[j][N - 1 - i] = temp;
              }
          }
      }
  
  
      public static void moves(String s, int i, int[] movx, int[] movy, int x, int y) {
          if (i >= s.length())
              return;
          //System.out.println(x+" hello "+y);
          if (s.charAt(i) == 'L') {
              movy[i] = y;
              movx[i] = x - 1;
              moves(s, i + 1, movx, movy, x - 1, y);
          } else if (s.charAt(i) == 'R') {
              movy[i] = y;
              movx[i] = x + 1;
              moves(s, i + 1, movx, movy, x + 1, y);
          } else if (s.charAt(i) == 'U') {
              movy[i] = y + 1;
              movx[i] = x;
              moves(s, i + 1, movx, movy, x, y + 1);
          } else {
              movy[i] = y - 1;
              movx[i] = x;
              moves(s, i + 1, movx, movy, x, y - 1);
          }
  
      }
  
  
  
  
  
      public static boolean checker(String s1, String s2, int[] arr, int mid) {
          String s = "";
          int N = s1.length();
          boolean[] visited = new boolean[N];
          for (int i = 0; i <= mid; i++)
              visited[arr[i] - 1] = true;
          for (int i = 0; i < N; i++) {
              if (!visited[i])
                  s += s1.charAt(i);
          }
  
          int l = 0, index = -1;
          while (l < s2.length()) {
              if (s.indexOf(s2.charAt(l), index + 1) == -1)
                  return false;
              else {
                  index = s.indexOf(s2.charAt(l), index + 1);
                  ++l;
              }
          }
  
          return true;
      }
  
      public static int check(ArrayList<Integer> possible, int X, int start) {
          int l = start, r = possible.size() - 1;
  
          while (l <= r) {
              int mid = (l + r) / 2;
              if (possible.get(mid) > X) {
                  if (mid - 1 >= start && possible.get(mid - 1) > X)
                      r = mid - 1;
                  else
                      return mid;
              } else
                  l = mid + 1;
          }
  
          return -1;
      }
  
  
      public static int binse(div[] arr, int X, int N) {
          int l = 0, r = N - 1;
  
          if(arr[N-1].x<=X)
              return N;
          if(arr[0].x>X)
              return 0;
          while (l <= r) {
              int mid = (l + r) / 2;
  //            if(N==2)
  //            {
  //                System.out.println(arr[mid].x+" hello "+X);
  //            }
              if(arr[mid].x<=X)
              {
                  if(mid+1<N && arr[mid+1].x<=X)
                      l=mid+1;
                  else
                  {
                      //System.out.println(X+" "+mid);
  
                      return mid+1;
                  }
              }
  
              else
                  r=mid-1;
          }
          return -1;
      }
  
  
      public static long dp(long[][] dp, int X, int[] arr, int index, long mod) {
          //System.out.println(index+" "+X);
          if (dp[index][X] != -1)
              return dp[index][X];
          int index1 = index + 1;
          int plus = (X - arr[index1] + 10) % 10;
          long ans = dp(dp, plus, arr, index - 1, mod) % mod;
          for (int i = 0; i < 10; i++) {
              if ((arr[index1] * i) % 10 == X)
                  ans = (ans % mod + dp(dp, i, arr, index - 1, mod) % mod) % mod;
          }
  
          dp[index][X] = ans;
          return ans;
  
  
      }
  
      public static long gcd(long a, long b) {
          if (b == 0)
              return a;
  
          return gcd(b, a % b);
      }
  
      public static int check(int x, ArrayList<ArrayList<Integer>> arr, int parent, int dist, long[] ans, int[] child) {
          ans[0] += dist;
          int c = 0;
          for (int i : arr.get(x)) {
              if (i != parent)
                  c += check(i, arr, x, dist + 1, ans, child);
          }
  
          child[x] = c + 1;
          return c + 1;
      }
  
      public static void check(int x, int parent, ArrayList<ArrayList<Integer>> arr, int[] child, long[] ans) {
          ans[x] = ans[parent] - (child[x]) + (arr.size() - child[x]);
  
          for (int i : arr.get(x)) {
              if (i != parent) {
                  check(i, x, arr, child, ans);
              }
          }
      }
  
      public static void leftRotatebyOne(int arr[], int n) {
          int i, temp;
          temp = arr[0];
          for (i = 0; i < n - 1; i++)
              arr[i] = arr[i + 1];
          arr[n - 1] = temp;
      }
  
      public static void tick(char[][] ch, int N, int M, int x, int y, int k, int[][] copy) {
  
          int c = 1, size = 0;
          //System.out.println(x+" "+y);
          while (x - c >= 0 && y - c >= 0 && y + c < M && ch[x - c][y - c] == '*' && ch[x - c][y + c] == '*') {
              ++size;
  
              ++c;
  
          }
          //System.out.println(size);
          c -= 1;
          while (c >= 0) {
  
              copy[x - c][y - c] = Math.max(copy[x - c][y - c], size);
              copy[x - c][y + c] = Math.max(copy[x - c][y + c], size);
  
              --c;
          }
  
  
      }
  
      public static long dp(ArrayList<Integer> arr,HashMap<Integer,Long> hp)
      {
          if(arr.size()==0)
              return 0;
          long[]dp=new long[arr.size()];
          dp[0]=hp.get(arr.get(0))*arr.get(0);
          if(arr.size()==1)
              return dp[0];
          dp[1]=Math.max(arr.get(1)*(hp.get(arr.get(1))),arr.get(0)*(hp.get(arr.get(0))));
          for(int i=2;i<arr.size();i++)
          {
              int X=arr.get(i);
              dp[i]=Math.max(X*(hp.get(X))+dp[i-2],dp[i-1]);
              dp[i]=Math.max(dp[i],dp[i-2]+X*hp.get(X));
          }
  //        for(int i=0;i<arr.size();i++)
  //            System.out.println(dp[i]);
  
          return dp[arr.size()-1];
      }
  
      static int power(int x, int y, int p)
      {
  
          // Initialize result
          int res = 1;
  
          // Update x if it is more than or
          // equal to p
          x = x % p;
  
          while (y > 0) {
  
              // If y is odd, multiply x
              // with result
              if (y % 2 == 1)
                  res = (res * x) % p;
  
              // y must be even now
              y = y >> 1; // y = y/2
              x = (x * x) % p;
          }
  
          return res;
      }
  
      // Returns n^(-1) mod p
      static int modInverse(int n, int p)
      {
          return power(n, p - 2, p);
      }
  
      // Returns nCr % p using Fermat's
      // little theorem.
      static int nCrModPFermat(int n, int r,
                               int p)
      {
  
          if (n<r)
              return 0;
          // Base case
          if (r == 0)
              return 1;
  
          // Fill factorial array so that we
          // can find all factorial of r, n
          // and n-r
          int[] fac = new int[n + 1];
          fac[0] = 1;
  
          for (int i = 1; i <= n; i++)
              fac[i] = fac[i - 1] * i % p;
  
          return (fac[n] * modInverse(fac[r], p)
                  % p * modInverse(fac[n - r], p)
                  % p)
                  % p;
      }
  
      public static int check(int N,int[] dp)
      {
          if(N==0)
              return 0;
          if(dp[N]!=-1)
              return dp[N];
  
          if(N<10)
              return 1;
          int max=Integer.MAX_VALUE;
          int X=N;
          while(X>0)
          {
              int digit=X%10;
              if(digit!=0)
              {
                  if(dp[N-digit]==-1)
                      max=Math.min(max,check(N-digit,dp));
                  else
                      max=Math.min(max,dp[N-digit]);
              }
              X=X/10;
  
          }
          dp[N]=max+1;
          return max+1;
      }
  
      public static int check(int a,int b,int k,int[][] dp,int index,int N,int[] length)
      {
          if(index>=N)
              return 0;
          if(k==1)
          {
              if(N-index<a || N-index>b)
              {
                  dp[index][k]=0;
                  return 0;
              }
              else
              {
                  dp[index][k]=1;
                  length[index]=N-index;
                  return 1;
              }
          }
          if(dp[index][k]!=-1)
              return dp[index][k];
  
          int ans=0;
          for(int i=a;i<=b;i++)
          {
              if(check(a,b,k-1,dp,index+i,N,length)==1)
              {
                  length[index]=i;
                  ans=1;
              }
          }
          if(ans>=1)
          {
              dp[index][k]=1;
              return 1;
          }
          else
          {
              dp[index][k]=0;
              return 0;
          }
      }
  
      public static long[][] ncr(int n,int r)
      {
          long[][] dp=new long[n+1][r+1];
          for(int i=0;i<=n;i++)
              dp[i][0]=1;
          for(int i=1;i<=n;i++)
          {
              for(int j=1;j<=r;j++)
              {
                  if(j>i)
                      continue;
                  dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
              }
          }
  
          return dp;
  
      }
      public static String answer(String s1,String s2)
      {
          int index=0;
          boolean status=true;
          for(int i=0;i<s2.length();i++)
          {
              if(s1.indexOf(s2.charAt(i),index)==-1)
              {
                  status=false;
              }
              else
              {
                  index=s1.indexOf(s2.charAt(i),index)+1;
              }
          }
          if(status)
              return "automaton";
  
  
          String arr1[]=s1.split("");
          String arr2[]=s2.split("");
          Arrays.sort(arr1);
          Arrays.sort(arr2);
          if(Arrays.equals(arr1,arr2))
              return "array";
  
          HashMap<Character,Integer> hp=new HashMap<>();
          for(int i=0;i<s2.length();i++)
          {
              hp.put(s2.charAt(i),0);
          }
          for(int i=0;i<s2.length();i++)
          {
              if(s1.indexOf(s2.charAt(i),hp.get(s2.charAt(i)))==-1)
              {
                  return "need tree";
              }
              else
              {
                  hp.put(s2.charAt(i),s1.indexOf(s2.charAt(i),hp.get(s2.charAt(i)))+1);
              }
          }
  
          return "both";
  
  
  
      }
      static boolean status=false;
      static int x1=-1,y1=-1;
      public static int dfs(ArrayList<ArrayList<Integer>> arr,int X,int[] ans,int value,int parent)
      {
          int xor=ans[X];
          for(int i:arr.get(X))
          {
              if(i!=parent)
              {
                  int x=dfs(arr,i,ans,value,X);
                  if(x==-1)
                      return -1;
                  if(x==value)
                  {
                      x1=X;
                      y1=i;
                      return -1;
                  }
                  xor=xor^x;
              }
          }
  
  
  
          return xor;
      }
  
      public static boolean prime(long N)
      {
          int c=0;
          for(int i=2;i*i<=N;i++)
          {
              if(N%i==0)
                  ++c;
          }
  
          return c==0;
      }
      static int[] c;
      static boolean sta=true;
      public static int dfs(ArrayList<ArrayList<Integer>> arr,int N,int j,int[] status,boolean[] visited)
      {
          Queue<Integer> queue=new LinkedList<>();
          queue.add(j);
          status[j]=1;
          visited[j]=true;
          int[] color=new int[2];
          while(queue.size()>0)
          {
              int temp=queue.poll();
              if(temp<N)
                  color[status[temp]]++;
              for(int i:arr.get(temp))
              {
                  if(visited[i])
                  {
                      if(status[i]==status[temp])
                          return -1;
                  }
                  else
                  {
                      queue.add(i);
                      status[i]=1-status[temp];
                      visited[i]=true;
                  }
              }
          }
  
          return Math.max(color[0],color[1]);
      }
  
      public static boolean check(String s,int N,long D,long C,long M)
      {
          int index=s.lastIndexOf('D');
          for(int i=0;i<=index;i++)
          {
              if(s.charAt(i)=='D' && D>0)
              {
                  D-=1;
                  C+=M;
              }
              else if(s.charAt(i)=='C' && C>0)
              {
                  C-=1;
              }
              else
                  return false;
          }
  
          return true;
      }
  
  
  
  
      public static boolean checkbounds(int x,int y,int N,int M)
      {
          return x>=0 && x<N && y>=0 && y<M;
      }
  
      public static void dfs(int x,int y,char[][] grid,boolean[][] visited,int N,int M)
      {
          visited[x][y]=true;
          if(checkbounds(x+1,y,N,M) && !visited[x+1][y] && grid[x+1][y]=='.')
              dfs(x+1,y,grid,visited,N,M);
          if(checkbounds(x-1,y,N,M) && !visited[x-1][y] && grid[x-1][y]=='.')
              dfs(x-1,y,grid,visited,N,M);
          if(checkbounds(x,y+1,N,M) && !visited[x][y+1] && grid[x][y+1]=='.')
              dfs(x,y+1,grid,visited,N,M);
          if(checkbounds(x,y-1,N,M) && !visited[x][y-1] && grid[x][y-1]=='.')
              dfs(x,y-1,grid,visited,N,M);
      }
  
      public static int bin(ArrayList<Integer> arr,int search)
      {
          int l=0,r=arr.size()-1;
          if(search<arr.get(0))
              return -1;
          if(search>arr.get(r-1))
              return r+1;
          while(l<=r)
          {
              int mid=(l+r)/2;
              if(arr.get(mid)>search)
              {
                  if(mid-1>=0 && arr.get(mid-1)>search)
                      r=mid-1;
                  else
                      return mid;
              }
              else
                  l=mid+1;
          }
  
          return -1;
      }
  
  
      public static int mcbc(ArrayList<Long> arr,long search,int N,int lower)
      {
          if(search>=arr.get(N))
              return N;
  
          if(search<=arr.get(lower))
              return lower;
          int l=lower;
          int r=N;
          while(l<=r)
          {
              int mid=(l+r)/2;
              if(arr.get(mid)==search)
              {
                  return mid;
              }
  
              if(arr.get(mid)>search)
              {
                  if(mid-1>=lower && arr.get(mid-1)>=search)
                      r=mid-1;
                  else
                  {
                      if(mid-1>=lower)
                      {
                          if (Math.abs(search - arr.get(mid)) < Math.abs(search - arr.get(mid - 1)))
                              return mid;
                          else
                              return mid - 1;
                      }
                      else
                          return mid;
                  }
              }
  
              else if(arr.get(mid)<search)
              {
                  if(mid+1<=N && arr.get(mid+1)<=search)
                      l=mid+1;
                  else
                  {
                      if(mid+1<=N)
                      {
                          if (Math.abs(search - arr.get(mid)) < Math.abs(search - arr.get(mid + 1)))
                              return mid;
                          else
                              return mid + 1;
                      }
                      else
                          return mid;
                  }
              }
          }
  
          return -1;
  
      }
  
      public static int check(String s,char ch)
      {
          int l=0,r=s.length()-1;
          int c=0;
          while(l<r)
          {
              if(s.charAt(l)!=s.charAt(r))
              {
                  if(s.charAt(l)==ch)
                  {
                      ++c;
                      ++l;
                  }
                  else if(s.charAt(r)==ch)
                  {
                      ++c;
                      --r;
                  }
                  else
                  {
                      return -1;
                  }
              }
              else
              {
                  ++l;
                  --r;
              }
          }
  
          return c;
  
      }
  
      public static boolean getbounds(int x,int y,int N,int M)
      {
          return x>=0 && x<N && y>=0 && y<M;
      }
  
      static boolean cycle=false;
  
      public static void check(int x1,int y1,String[][] s,boolean[][] visited,int N,int M,int[] xdiff,int[] ydiff,div[][] ans,int index)
      {
          Queue<div> queue1=new LinkedList<>();
          Queue<div> queue2=new LinkedList<>();
          visited[x1][y1]=true;
          queue1.add(new div(x1,y1));
          queue2.add(new div(x1,y1));
          int c=0;
          while(queue1.size()>0)
          {
              div temp=queue1.poll();
              //System.out.println("hello");
              int x=temp.x;
              int y=temp.y;
              ++c;
              for(int i=0;i<4;i++)
              {
                  if(getbounds(x+xdiff[i],y+ydiff[i],N,M))
                  {
                      if(!visited[x+xdiff[i]][y+ydiff[i]] && s[x+xdiff[i]][y+ydiff[i]].equals("."))
                      {
                          queue1.add(new div(x+xdiff[i],y+ydiff[i]));
                          queue2.add(new div(x+xdiff[i],y+ydiff[i]));
                          visited[x+xdiff[i]][y+ydiff[i]]=true;
                      }
                  }
              }
          }
  
          div com=new div(index,c);
  
          while(queue2.size()>0)
          {
  
              div temp=queue2.poll();
              int x=temp.x;
              int y=temp.y;
              ans[x][y]=com;
          }
  
      }
  
      static int connected=0;
  
      public static int edges(ArrayList<ArrayList<Integer>> arr,int x,boolean[] visited)
      {
          ++connected;
          int sum=arr.get(x).size();
          visited[x]=true;
          for(int i:arr.get(x))
          {
              if(!visited[i])
                  sum+=edges(arr,i,visited);
          }
  
          return sum;
  
      }
  
      public static TreeNode build(TreeNode A,TreeNode B)
      {
          if(A==null && B==null)
              return null;
          if(A!=null && B==null)
              return A;
          if(B!=null && A==null)
              return B;
          TreeNode left=build(A.left,B.left);
          TreeNode right=build(A.right,B.right);
          B.left=left;
          B.right=right;
          return B;
  
      }
  
      public static TreeNode check(TreeNode root1,TreeNode root2)
      {
          return build(root1,root2);
      }
  
      public static int check(String str1,String str2)
      {
          if(str1.length()!=str2.length())
              return -1;
          int[] count1=new int[26];
          int[] count2=new int[26];
          for(int i=0;i<str1.length();i++)
          {
              count1[str1.charAt(i)-97]++;
              count2[str2.charAt(i)-97]++;
          }
  
          for(int i=0;i<26;i++)
          {
              if(count1[i]!=count2[i])
                  return -1;
          }
  
          int i = str1.length() - 1;
          int j = str2.length() - 1;
          int ans=0;
          while(i >= 0)
          {
              if(str1.charAt(i) != str2.charAt(j))
                  ans++;
              else
                  j--;
              i--;
          }
          return ans;
      }
  
  
  
  
  
  
  
      public static void main(String[] args) throws IOException {
          Reader.init(System.in);
          BufferedWriter output = new BufferedWriter(new OutputStreamWriter(System.out));
          int T=Reader.nextInt();
          for(int m=1;m<=T;m++)
          {
              int N=Reader.nextInt();
              int[] arr=new int[N];
              for(int i=0;i<N;i++)
              {
                  arr[i]=Reader.nextInt();
              }
              if(N%2==0)
              {
                  output.write("YES"+"\n");
              }
              else
              {
                  boolean c=false;
                  for(int i=0;i<N-1;i++)
                  {
                      if(arr[i]>=arr[i+1])
                      {
                          c=true;
                          break;
                      }
                  }
  
                  if(c)
                      output.write("YES"+"\n");
                  else
                      output.write("NO"+"\n");
              }
  
              //output.write(c+"\n");
  
  
          }
  
  
  
  
  
  
  
  
  
  
  
  
  
          output.flush();
  
      }
  }
  
  
  
  class Reader {
      static BufferedReader reader;
      static StringTokenizer tokenizer;
  
      static void init(InputStream input) {
          reader = new BufferedReader(
                  new InputStreamReader(input));
          tokenizer = new StringTokenizer("");
      }
  
      static String next() throws IOException {
          while (!tokenizer.hasMoreTokens()) {
              tokenizer = new StringTokenizer(
                      reader.readLine());
          }
          return tokenizer.nextToken();
      }
  
      static int nextInt() throws IOException {
          return Integer.parseInt(next());
      }
  
      static long nextLong() throws IOException {
          return Long.parseLong(next());
      }
  
      static double nextDouble() throws IOException {
          return Double.parseDouble(next());
      }
  }
  
  
  class sortat implements Comparator<Long>
  {
      public int compare(Long o1,Long o2)
      {
          if(Math.abs(o1)<Math.abs(o2))
              return -1;
          else if(Math.abs(o1)>Math.abs(o2))
              return 1;
          else
              return 0;
      }
  }
  
  class div {
      int x, y;
  
      div(int x1,int z1) {
          x = x1;
          y=z1;
  
      }
  }
  
  class TreeNode
  {
      int data;
      TreeNode left;
      TreeNode right;
      TreeNode(int data)
      {
          left=null;
          right=null;
          this.data=data;
      }
  }
  