Find maximum QAZ

qaz is a value for a number where this number is less than the other next values which have indexes larger than the index of this number.
For example: 33 , 25 , 26 , 58 , 41 , 59 -> qaz of (33) = 3 where 33 less than 3 numbers (58 , 41 , 59), qaz of (25) = 4 and not 5 because the index of 33 is less than the index of 25, qaz of (26) = 3 , qaz of (58) = 1 , qaz of (41) = 1 , qaz of (59) = 0.
The question is to find the max qaz.
It can be solved simply using 2 loops which takes time of O(n^2).
That's ok but how can we solve this problem in O(nlogn). 

When we need to solve some problem using O(nlogn), either it is sort (merge sort, quick sort...) or divide and conquer (technically merge sort is also a divide and conquer approach). This problem doesn't require us to "sort" the array, actually we cannot sort it, otherwise how can we preserve the original index?

Recursively halve the array (divide from the middle). Before merge (conquer), store the minimum and maximum QAZ of both the left and the right part. When merge, note only the QAZ at the left part can change (the right part always has the larger index compare to the left part). The element with the max QAZ will always be a local minimum, i.e., it will be minimum value among all elements that have index larger than it. So we only need to consider the QAZ for the left min each time we merge two parts. If the left min is smaller than the right min, that means all elements in the right part are larger than left min, thus we increment left.qaz by the number of elements in the right part. Otherwise, do a linear scan in the right part to find all elements that are larger than left min. Return the struct (between left and right) that has the larger QAZ.

public class QAZ {
 private static class QAZstruct {
  int min;
  int qaz;
  public QAZstruct(int min, int qaz) {
   this.min = min;
   this.qaz = qaz;
  }
 }
 public static int maxQAZ(int[] array) {
  if (array == null || array.length <= 1)
   return 0;
  return getMaxQAZ(array, 0, array.length - 1).qaz;
 }
 
 private static QAZstruct getMaxQAZ(int[] array, int start, int end) {
  if (end <= start)
   return new QAZstruct(array[end], 0);
  
  if (end == start + 1)
   return array[start] < array[end] ? new QAZstruct(array[start], 1) : new QAZstruct(array[end], 0);
  int mid = (start + end) / 2;
  QAZstruct left = getMaxQAZ(array, start, mid);
  QAZstruct right = getMaxQAZ(array, mid + 1, end);
  //if the left min is smaller than right min, then every element in the right part is greater than the left minimum, thus
  //qaz of the left part will increment by the number of elements in the right part
  if (left.min < right.min)
   return new QAZstruct(left.min, left.qaz + end - mid);
  for (int i = mid + 1; i <= end; i++) {
   if (array[i] > left.min)
    left.qaz++;
  }
  return left.qaz > right.qaz ? left : right;
   
 }
 public static void main(String[] args) {
  //int[] array = {28};
  //int[] array = {19, 37};
  int[] array = {37, 19};
  //int[] array = {97, 65, 23, 78, 46, 31};
  System.out.println(maxQAZ(array));
 }
}