/*
 * Given an unsorted array of size N.
 * Find the first element in array such that all of its left elements
 * are smaller and all right elements to it are greater than it.
 */
public class Median {
 public static void main(String[] args) {
//    int[] A = {8,5,6,9,10,11,4,12,13,14}; //Ans : 12
//    int[] A = {4,2,5,7}; //Ans : 5
//    int[] A = {11,9,12}; //Ans : -1
//    int[] A = {4,3,2,7,8,9}; //Ans : 7
//  int[] A = {1,2,3,4,5,6,7,8,9}; //Ans : 2
//    int[] A = {1,4,3,2,5,6,7,8,9}; //Ans : 5
  int[] A = {1,4,3,2,10,6,7,8,9}; //Ans : -1
  int len = A.length;
  int max = Integer.MIN_VALUE;
  int min = Integer.MAX_VALUE;
  int maxI = -1;
  int minI = -1;
  boolean found = false;
  for(int i = 0; i < len; i++) {
   int value = A[i];
   if(max < value) {
    max = value;
    maxI = i;
    found = true;
    continue;
   }
   if(min > value) {
    min = value;
    minI = i;
    found = true;
   }
   if(max > value && maxI < i)
    found = false;
  }
  if(maxI > minI && len-1 > minI+1 && minI+1 > 0 && found)
   System.out.println(A[minI+1]);
  else if(minI == -1 && found) {
   if(A[0] < A[1])
    System.out.println(A[1]);
  } else
   System.out.println(-1);
 }
}

 Bit simpler way - Traverse left to right to mark the index of largest number till the current index. Then traverse right to left to check if the current number is minimum & also check maxNum[curIndex] == -1