Given an unsorted array arr[] of size n , write a program to find the max (j - i) difference between indices such that j > i and arr[j] > arr[i] .

Example 1

Input: arr[] = [72, 8, 10, 3, 2, 81, 30, 1, 32]
Output: 7 (j = 8, i = 1)
Explanation: max(j - i) = 8 - 1 = 7 such that 8 > 1 and arr[8] > arr[1] are true.

Example 2

Input: arr[] = [5, 2, 3, 5, 4, 6, 7, 8, 19, 0]
Output: 8 (j = 8, i = 0)
Explanation: max(j - i) = 8 - 0 = 8 such that 8 > 0 and arr[8] > arr[0] are true.

Example 3

Input: arr[] = [0, 2, 3, 4, 5, 8, 9]
Output: 6 (j = 6, i = 0)
Explanation: In an array sorted in increasing order, the max(j - i) is the difference between last and first index. Here, max(j - i) = 6 - 0 such that 6 > 0 and arr[6] > arr[0] are true.

Example 4

Input: arr[] = [11, 8, 5, 4, 2, 1]
Output: -1 
Explanation: In an array sorted in decreasing order, it is not possible to have max(j - i) such that arr[j] > arr[i] and j > i. So, the answer is -1.