Maximum Index Difference

You are given an array A consisting of N integers. Your task is to find the maximum value of the index difference j - i such that A[j] \geq A[i] and j is greater than or equal to i. If no such pair exists, the answer is 0.

Example:
For N = 9 and A = [34, 8, 10, 3, 2, 80, 30, 33, 1], the maximum difference is 6 because the condition holds with i = 1 (where A[1]=8) and j = 7 (where A[7]=33).

The intended solution should run in linear time by precomputing arrays for the minimums from the left and maximums from the right.

inputFormat

The first line of input contains an integer N which denotes the number of elements in the array. The second line contains N space-separated integers representing the array A.

outputFormat

Output a single integer which is the maximum index difference (j - i) such that A[j] \geq A[i]. If no valid pair exists, output 0.

9
34 8 10 3 2 80 30 33 1

6