Given an array A[] of N positive integers. The task is to find the maximum of j - i subjected to the constraint of A[i] < A[j] and i < j.
 
Example 1:
Input:
N = 2
A[] = {1, 10}
Output:
1
Explanation:
A[0]<A[1] so (j-i) is 1-0 = 1.
Example 2:
Input:
N = 9
A[] = {34, 8, 10, 3, 2, 80, 30, 33, 1}
Output:
6
Explanation:
In the given array A[1] < A[7]
satisfying the required 
condition(A[i] < A[j]) thus giving 
the maximum difference of j - i 
which is 6(7-1).
 
Your Task:
The task is to complete the function maxIndexDiff() which finds and returns maximum index difference. Printing the output will be handled by driver code. Return 0 in case no such index is found.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 10^{7}
0 ≤ A[i] ≤ 10^{9}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Starter code: #User function Template for python3



class Solution:

    #Complete this function

    # Function to find the maximum index difference.

    def maxIndexDiff(self,A, N): 

        ##Your code here

Solutions:
class Solution:

	def maxIndexDiff(self, A, N):
		left = [0] * N
		right = [0] * N
		diff = 0
		(mini, maxi) = (A[0], A[N - 1])
		for i in range(N - 1, -1, -1):
			if A[i] >= maxi:
				maxi = A[i]
			right[i] = maxi
		(i, j) = (0, 0)
		while i < N and j < N:
			if A[i] <= right[j]:
				diff = max(diff, j - i)
				j += 1
			else:
				i += 1
		return diff


class Solution:

	def maxIndexDiff(self, A, N):
		left = [0] * N
		right = [0] * N
		left[0] = A[0]
		for i in range(1, N):
			left[i] = min(left[i - 1], A[i])
		right[N - 1] = A[N - 1]
		for i in range(N - 2, -1, -1):
			right[i] = max(right[i + 1], A[i])
		i = 0
		j = 0
		ans = -1
		while i < N and j < N:
			if left[i] <= right[j]:
				ans = max(ans, j - i)
				j += 1
			else:
				i += 1
		return ans


class Solution:

	def maxIndexDiff(self, A, N):
		left_min = [0] * N
		right_max = [0] * N
		left_min[0] = A[0]
		for i in range(1, N):
			left_min[i] = min(A[i], left_min[i - 1])
		right_max[N - 1] = A[N - 1]
		for j in range(N - 2, -1, -1):
			right_max[j] = max(A[j], right_max[j + 1])
		i = j = max_diff = 0
		while i < N and j < N:
			if left_min[i] <= right_max[j]:
				max_diff = max(max_diff, j - i)
				j += 1
			else:
				i += 1
		return max_diff


class Solution:

	def maxIndexDiff(self, A, N):
		lmin = [None] * N
		rmax = [None] * N
		lmin[0] = A[0]
		for i in range(1, N):
			lmin[i] = min(lmin[i - 1], A[i])
		rmax[N - 1] = A[N - 1]
		for i in reversed(range(N - 1)):
			rmax[i] = max(A[i], rmax[i + 1])
		i = 0
		j = 0
		m = -1
		while i < N and j < N:
			if lmin[i] <= rmax[j]:
				m = max(m, j - i)
				j += 1
			else:
				i += 1
		return m


class Solution:

	def maxIndexDiff(self, A, N):
		n = N
		if n == 1:
			return 0
		s = 0
		L = [A[0]]
		R = [-1] * N
		r = A[N - 1]
		for i in range(1, n):
			L.append(min(A[i], L[i - 1]))
		for j in range(n - 1, -1, -1):
			if r < A[j]:
				r = A[j]
			R[j] = max(r, A[j])
		(i, j) = (0, 0)
		while i < n and j < n:
			if L[i] <= R[j]:
				w = j - i
				s = max(s, w)
				j += 1
			else:
				i += 1
		return s


class Solution:

	def maxIndexDiff(self, arr, n):
		minarray = [0] * n
		maxarray = [0] * n
		minarray[0] = arr[0]
		for i in range(1, n):
			minarray[i] = min(arr[i], minarray[i - 1])
		maxarray[n - 1] = arr[n - 1]
		for i in range(n - 2, -1, -1):
			maxarray[i] = max(arr[i], maxarray[i + 1])
		(i, j) = (0, 0)
		ans = 0
		while j < n and i < n:
			if minarray[i] <= maxarray[j]:
				ans = max(ans, j - i)
				j = j + 1
			else:
				i = i + 1
		return ans


class Solution:

	def maxIndexDiff(self, arr, n):
		LMin = [0 for i in range(n)]
		LMin[0] = arr[0]
		for i in range(1, n):
			LMin[i] = min(arr[i], LMin[i - 1])
		RMax = [0 for i in range(n)]
		RMax[n - 1] = arr[n - 1]
		for i in range(n - 2, -1, -1):
			RMax[i] = max(arr[i], RMax[i + 1])
		(i, j, maxDiff) = (0, 0, -1)
		while j < n and i < n:
			if LMin[i] <= RMax[j]:
				maxDiff = max(maxDiff, j - i)
				j = j + 1
			else:
				i = i + 1
		return maxDiff


class Solution:

	def maxIndexDiff(self, array, n):
		leftMin = [0] * n
		leftMin[0] = array[0]
		for i in range(1, n):
			leftMin[i] = min(leftMin[i - 1], array[i])
		maxdifference = -1
		i = j = n - 1
		while i >= 0 and j >= 0:
			if array[j] >= leftMin[i]:
				maxdifference = max(maxdifference, j - i)
				i -= 1
			else:
				j -= 1
		return maxdifference


class Solution:

	def maxIndexDiff(self, a, n):
		sarr = [a[0]]
		cn = a[0]
		for i in range(1, n):
			if a[i] < cn:
				cn = a[i]
			sarr.append(cn)
		barr = [a[n - 1]]
		cn = a[n - 1]
		for i in range(n - 2, -1, -1):
			if a[i] > cn:
				cn = a[i]
			barr.append(cn)
		barr = list(reversed(barr))
		mx = -1
		(i, j) = (0, 0)
		while i < n and j < n:
			if barr[i] >= sarr[j]:
				mx = max(mx, i - j)
				i += 1
			else:
				j += 1
		return mx


class Solution:

	def maxIndexDiff(self, arr, n):
		left_arr = [arr[0]] * n
		right_arr = [arr[n - 1]] * n
		i = 1
		while i < n:
			left_arr[i] = min(arr[i], left_arr[i - 1])
			i += 1
		i -= 1
		while i > 0:
			i -= 1
			right_arr[i] = max(right_arr[i + 1], arr[i])
		left = right = res = 0
		while left < n and right < n:
			if left_arr[left] <= right_arr[right]:
				res = max(res, right - left)
				right += 1
			else:
				left += 1
		return res


class Solution:

	def maxIndexDiff(self, A, N):
		fm = [0] * N
		fm[0] = A[0]
		for i in range(1, len(A)):
			fm[i] = min(fm[i - 1], A[i])
		fn = [0] * N
		fn[N - 1] = A[N - 1]
		for i in range(len(A) - 2, -1, -1):
			fn[i] = max(fn[i + 1], A[i])
		i = 0
		j = 0
		k = -1
		while i < N and j < N:
			if fm[i] <= fn[j]:
				k = max(j - i, k)
				j += 1
			else:
				i += 1
		return k


class Solution:

	def maxIndexDiff(self, arr, n):
		lMin = [9999999] * n
		rMax = [-9999999] * n
		for i in range(0, n):
			if i == 0:
				lMin[i] = arr[i]
			else:
				lMin[i] = min(lMin[i - 1], arr[i])
		for i in range(n - 1, -1, -1):
			if i == n - 1:
				rMax[i] = arr[i]
			else:
				rMax[i] = max(rMax[i + 1], arr[i])
		left = 0
		right = 0
		result = 0
		while left <= n - 1 and right <= n - 1:
			if right >= left and arr[left] <= arr[right]:
				result = max(result, right - left)
			if lMin[left] > rMax[right]:
				left += 1
			else:
				right += 1
		return result


class Solution:

	def maxIndexDiff(self, arr, n):
		rightMax = [0] * n
		rightMax[n - 1] = arr[n - 1]
		for i in range(n - 2, -1, -1):
			rightMax[i] = max(rightMax[i + 1], arr[i])
		maxDist = -2 ** 31
		i = 0
		j = 0
		while i < n and j < n:
			if rightMax[j] >= arr[i]:
				maxDist = max(maxDist, j - i)
				j += 1
			else:
				i += 1
		return maxDist


class Solution:

	def maxIndexDiff(self, A, N):
		if N == 1:
			return 0
		diff = 0
		a = [A[0]]
		b = [-1] * N
		for i in range(1, N):
			a.append(min(A[i], a[i - 1]))
		for j in range(N - 1, -1, -1):
			if A[N - 1] < A[j]:
				A[N - 1] = A[j]
			b[j] = max(A[N - 1], A[j])
		i = j = 0
		while j < N and i < N:
			if a[i] <= b[j]:
				sub = j - i
				diff = max(diff, sub)
				j = j + 1
			else:
				i = i + 1
		return diff


class Solution:

	def maxIndexDiff(self, A, N):
		max_right = [-1] * N
		max_right[N - 1] = A[N - 1]
		for i in range(N - 2, -1, -1):
			max_right[i] = max(max_right[i + 1], A[i])
		maxi = 0
		i = 0
		j = 0
		while i < N and j < N:
			if max_right[j] >= A[i]:
				maxi = max(maxi, j - i)
				j += 1
			else:
				i += 1
		maxi = max(maxi, j - i - 1)
		return maxi


class Solution:

	def maxIndexDiff(self, A, N):
		ans = 0
		max_element = [0] * N
		max_element[-1] = A[-1]
		for i in range(N - 2, -1, -1):
			max_element[i] = max(A[i], max_element[i + 1])
		(i, j) = (0, 0)
		while i < N and j < N:
			if A[i] <= max_element[j]:
				ans = max(ans, j - i)
				j += 1
			else:
				i += 1
		return ans


class Solution:

	def maxIndexDiff(self, A, N):
		maxarr = [0] * N
		maxarr[-1] = A[-1]
		for i in range(N - 2, -1, -1):
			maxarr[i] = max(A[i], maxarr[i + 1])
		maxx = 0
		i = 0
		j = 0
		while i < N and j < N:
			if maxarr[j] >= A[i]:
				maxx = max(maxx, j - i)
				j += 1
			else:
				i += 1
		return maxx


class Solution:

	def maxIndexDiff(self, arr, n):
		Rmax = [0 for i in range(n)]
		Rmax[-1] = arr[-1]
		for i in range(n - 2, -1, -1):
			Rmax[i] = max(Rmax[i + 1], arr[i])
		(i, j, maxdiff) = (0, 0, -1)
		while i < n and j < n:
			if arr[i] <= Rmax[j]:
				maxdiff = max(maxdiff, j - i)
				j = j + 1
			else:
				i = i + 1
		return maxdiff


class Solution:

	def maxIndexDiff(self, A, N):
		l = []
		r = []
		mi = A[0]
		l.append(mi)
		for i in range(1, N):
			if A[i] < mi:
				mi = A[i]
				l.append(mi)
			else:
				l.append(mi)
		mx = A[-1]
		r.append(mx)
		for i in range(N - 2, -1, -1):
			if A[i] > mx:
				mx = A[i]
				r.append(mx)
			else:
				r.append(mx)
		i = 0
		j = 0
		r.reverse()
		ans = 0
		while i < N and j < N:
			if l[i] <= r[j]:
				ans = max(ans, j - i)
				j += 1
			else:
				i += 1
				j += 1
		return ans


class Solution:

	def maxIndexDiff(self, A, N):
		s = []
		for i in range(len(A) - 1):
			if not s or A[s[-1]] >= A[i]:
				s.append(i)
		maxx = 0
		for i in range(len(A) - 1, -1, -1):
			while len(s) and A[s[-1]] <= A[i]:
				maxx = max(maxx, i - s[-1])
				s.pop()
		return maxx


class Solution:

	def maxIndexDiff(self, A, N):
		Lmin = [0] * N
		Rmax = [0] * N
		Lmin[0] = A[0]
		for i in range(1, N):
			Lmin[i] = min(Lmin[i - 1], A[i])
		Rmax[N - 1] = A[N - 1]
		for j in range(N - 2, -1, -1):
			Rmax[j] = max(Rmax[j + 1], A[j])
		i = 0
		j = 0
		maxDiff = -1
		while j < N and i < N:
			if Lmin[i] <= Rmax[j]:
				maxDiff = max(maxDiff, j - i)
				j += 1
			else:
				i += 1
		return maxDiff


class Solution:

	def maxIndexDiff(self, arr, N):
		lft = [0] * N
		lft[0] = arr[0]
		for i in range(1, N):
			lft[i] = min(lft[i - 1], arr[i])
		i = N - 1
		j = N - 1
		mx = -99999
		while i >= 0 and j >= 0:
			if arr[j] >= lft[i]:
				mx = max(mx, j - i)
				i -= 1
			else:
				j -= 1
		return mx


class Solution:

	def maxIndexDiff(self, A, N):
		(maxArr, minArr) = ([0] * N, [0] * N)
		result = -1
		(maxArr[N - 1], minArr[0]) = (A[N - 1], A[0])
		for i in range(1, N):
			minArr[i] = min(minArr[i - 1], A[i])
		for j in range(N - 2, -1, -1):
			maxArr[j] = max(maxArr[j + 1], A[j])
		(i, j) = (0, 0)
		while i < N and j < N:
			if minArr[i] <= maxArr[j]:
				result = max(result, j - i)
				j += 1
			else:
				i += 1
		return result


class Solution:

	def maxIndexDiff(self, A, N):
		X = [0] * N
		Y = [0] * N
		X[0] = A[0]
		for i in range(1, N):
			X[i] = min(X[i - 1], A[i])
		Y[N - 1] = A[N - 1]
		for j in range(N - 2, -1, -1):
			Y[j] = max(Y[j + 1], A[j])
		i = j = 0
		max_val = 0
		while i < N and j < N:
			if X[i] <= Y[j]:
				max_val = max(max_val, j - i)
				j += 1
			else:
				i += 1
		return max_val


class Solution:

	def maxIndexDiff(self, A, N):
		if N == 1:
			return 0
		if N == 2:
			if A[0] <= A[1]:
				return 1
			else:
				return 0
		leftmin = [0] * N
		rightmax = [0] * N
		leftmin[0] = A[0]
		for i in range(1, N):
			leftmin[i] = min(leftmin[i - 1], A[i])
		rightmax[N - 1] = A[N - 1]
		for i in range(N - 2, -1, -1):
			rightmax[i] = max(rightmax[i + 1], A[i])
		i = 0
		j = 0
		res = 0
		while i <= j:
			if j == N:
				break
			if leftmin[i] <= rightmax[j]:
				res = max(res, j - i)
				j += 1
			else:
				i += 1
		return res


class Solution:

	def maxIndexDiff(self, A, N):
		st = []
		ans = -1
		for i in range(N):
			if not st or A[st[-1]] >= A[i]:
				st.append(i)
		i = N - 1
		while i >= 0:
			if st and A[st[-1]] <= A[i]:
				ans = max(i - st[-1], ans)
				st.pop()
			else:
				i -= 1
		return ans


class Solution:

	def maxIndexDiff(self, A, N):
		pre_min = [A[0]]
		cur_min = A[0]
		for i in range(1, N):
			if cur_min > A[i]:
				cur_min = A[i]
			pre_min.append(cur_min)
		post_max = [A[N - 1]]
		cur_max = A[N - 1]
		for i in range(N - 2, -1, -1):
			if cur_max < A[i]:
				cur_max = A[i]
			post_max.append(cur_max)
		post_max = post_max[::-1]
		(i, j) = (0, 0)
		max_diff = 0
		while j < N and i < N:
			if post_max[j] >= pre_min[i]:
				max_diff = max(max_diff, j - i)
				j = j + 1
			else:
				i = i + 1
		return max_diff


class Solution:

	def maxIndexDiff(self, A, N):
		ans = -1
		minleft = [None] * N
		minleft[0] = A[0]
		maxright = [None] * N
		maxright[-1] = A[-1]
		for i in range(1, N):
			minleft[i] = min(minleft[i - 1], A[i])
		for j in range(N - 2, -1, -1):
			maxright[j] = max(A[j], maxright[j + 1])
		i = 0
		j = 0
		while i < N and j < N:
			if maxright[j] >= minleft[i]:
				ans = max(ans, j - i)
				j += 1
			else:
				i += 1
		return ans


class Solution:

	def maxIndexDiff(self, A, N):
		minEle = [None] * N
		maxEle = [None] * N
		minEle[0] = A[0]
		for i in range(1, N):
			minEle[i] = min(minEle[i - 1], A[i])
		maxEle[-1] = A[-1]
		for i in range(N - 2, -1, -1):
			maxEle[i] = max(maxEle[i + 1], A[i])
		i = j = 0
		res = 0
		while i < N and j < N:
			if minEle[i] <= maxEle[j]:
				res = max(res, j - i)
				j += 1
			else:
				i += 1
		return res
		return res


class Solution:

	def maxIndexDiff(self, arr, N):
		idx = 0
		res = 0
		temp = N - 1
		while idx < temp // 2 + 1:
			if arr[idx] <= arr[temp]:
				if temp - idx > res:
					res = temp - idx
				temp = N - 1
				idx += 1
			else:
				temp = temp - 1
			if temp == idx:
				idx += 1
				temp = N - 1
		return res


class Solution:

	def maxIndexDiff(self, a, n):
		l = [0 for x in range(n)]
		s = []
		s.append(n - 1)
		for i in range(n - 2, -1, -1):
			if a[i] > a[s[-1]]:
				s.append(i)
			else:
				for j in s:
					if a[j] >= a[i]:
						l[i] = j - i
						break
		return max(l)


class Solution:

	def maxIndexDiff(self, A, N):
		right_max = [0 for i in range(N)]
		right_max[-1] = A[-1]
		for i in range(N - 2, -1, -1):
			right_max[i] = max(right_max[i + 1], A[i])
		res = 0
		i = j = 0
		while j < N:
			while j < N and A[i] <= right_max[j]:
				j += 1
			res = max(res, j - 1 - i)
			i += 1
		return res


class Solution:

	def maxIndexDiff(self, A, N):
		r = [0] * N
		l = [0] * N
		l[0] = A[0]
		r[N - 1] = A[N - 1]
		for i in range(1, N):
			l[i] = min(l[i - 1], A[i])
		for j in range(N - 2, -1, -1):
			r[j] = max(r[j + 1], A[j])
		a = -1
		i = 0
		j = 0
		while i < N and j < N:
			if l[i] <= r[j]:
				a = max(a, j - i)
				j = j + 1
			else:
				i = i + 1
		return a


class Solution:

	def maxIndexDiff(self, A, N):
		maxindex = 0
		rightmax = []
		rightmax = [0] * N
		rightmax[N - 1] = A[N - 1]
		for i in range(N - 2, -1, -1):
			rightmax[i] = max(rightmax[i + 1], A[i])
		i = 0
		j = 0
		while i < N and j < N:
			if A[i] <= rightmax[j]:
				maxindex = max(maxindex, j - i)
				j = j + 1
			else:
				i = i + 1
		return maxindex


class Solution:

	def maxIndexDiff(self, A, N):
		minleft = [None] * N
		maxright = [None] * N
		tempmin = A[0]
		tempmax = A[N - 1]
		for i in range(N):
			if A[i] < tempmin:
				tempmin = A[i]
			minleft[i] = tempmin
		for i in range(N - 1, -1, -1):
			if A[i] > tempmax:
				tempmax = A[i]
			maxright[i] = tempmax
		i = j = 0
		maxindex = 0
		while i < N and j < N:
			if minleft[i] > maxright[j]:
				i += 1
			else:
				maxindex = max(maxindex, j - i)
				j += 1
		return maxindex


class Solution:

	def maxIndexDiff(self, arr, n):
		leftMin = [0] * n
		leftMin[0] = arr[0]
		for i in range(1, n):
			leftMin[i] = min(leftMin[i - 1], arr[i])
		maxDist = -2 ** 32
		i = n - 1
		j = n - 1
		while i >= 0 and j >= 0:
			if arr[j] >= leftMin[i]:
				maxDist = max(maxDist, j - i)
				i -= 1
			else:
				j -= 1
		return maxDist


import sys

class Solution:

	def maxIndexDiff(self, A, N):
		min_left = [0] * N
		max_right = [0] * N
		min_left[0] = A[0]
		for i in range(1, N):
			min_left[i] = min(min_left[i - 1], A[i])
		max_right[N - 1] = A[N - 1]
		for i in range(N - 2, -1, -1):
			max_right[i] = max(max_right[i + 1], A[i])
		i = 0
		j = 0
		ans = -1
		while i < N and j < N:
			if min_left[i] <= max_right[j]:
				ans = max(ans, j - i)
				j += 1
			else:
				i += 1
		return ans


class Solution:

	def maxIndexDiff(self, A, N):
		lmin = [0] * N
		rmax = [0] * N
		lmin[0] = A[0]
		rmax[N - 1] = A[N - 1]
		for i in range(1, N):
			lmin[i] = min(lmin[i - 1], A[i])
		for i in range(N - 2, -1, -1):
			rmax[i] = max(rmax[i + 1], A[i])
		mx = -1
		(i, j) = (0, 0)
		while i < N and j < N:
			if lmin[i] <= rmax[j]:
				mx = max(mx, j - i)
				j += 1
			else:
				i += 1
		return mx


class Solution:

	def maxIndexDiff(self, A, N):
		(leftMin, rightMax) = ([0] * N, [0] * N)
		(leftMin[0], rightMax[N - 1]) = (A[0], A[N - 1])
		maxDiff = 0
		for i in range(1, N):
			leftMin[i] = min(leftMin[i - 1], A[i])
			rightMax[N - i - 1] = max(rightMax[N - i], A[N - i - 1])
		(i, j) = (0, 0)
		while i < N and j < N:
			if leftMin[i] <= rightMax[j]:
				maxDiff = max(maxDiff, j - i)
				j += 1
			else:
				i += 1
		return maxDiff


class Solution:

	def maxIndexDiff(self, A, N):
		n = N
		a = A
		index = dict()
		for i in range(n):
			if a[i] in index:
				index[a[i]].append(i)
			else:
				index[a[i]] = [i]
		a.sort()
		maxDiff = 0
		temp = n
		for i in range(n):
			if temp > index[a[i]][0]:
				temp = index[a[i]][0]
			maxDiff = max(maxDiff, index[a[i]][-1] - temp)
		return maxDiff


class Solution:

	def maxIndexDiff(self, arr, n):
		if n == 1:
			return 0
		if n == 2:
			return int(arr[1] >= arr[0])
		mini = [0] * n
		maxi = [0] * n
		mini[0] = arr[0]
		maxi[n - 1] = arr[n - 1]
		for i in range(1, n):
			mini[i] = min(mini[i - 1], arr[i])
		for j in range(n - 2, -1, -1):
			maxi[j] = max(maxi[j + 1], arr[j])
		i = j = 0
		dif = 0
		while i < n and j < n:
			if mini[i] <= maxi[j]:
				dif = max(dif, j - i)
				j += 1
			else:
				i += 1
		return dif


class Solution:

	def maxIndexDiff(self, A, N):
		lt = [A[0]]
		for i in range(1, N):
			lt.append(min(A[i], lt[-1]))
		gt = [0] * N
		gt[N - 1] = A[N - 1]
		for i in range(N - 2, -1, -1):
			gt[i] = max(A[i], gt[i + 1])
		m = 0
		(i, j) = (0, 0)
		while i < N and j < N:
			if gt[i] >= lt[j]:
				m = max(m, i - j)
				i += 1
			else:
				j += 1
		return m


class Solution:

	def maxIndexDiff(self, A, N):
		(mxa, mna) = ([0] * N, [0] * N)
		res = -1
		mxa[-1] = A[-1]
		mna[0] = A[0]
		(i, j) = (1, N - 2)
		while i < N and j >= 0:
			mna[i] = min(mna[i - 1], A[i])
			mxa[j] = max(mxa[j + 1], A[j])
			i += 1
			j -= 1
		(i, j) = (0, 0)
		while i < N and j < N:
			if mna[i] <= mxa[j]:
				res = max(res, j - i)
				j += 1
			else:
				i += 1
		return res


class Solution:

	def maxIndexDiff(self, A, N):
		maxFromRignt = [float('-inf')] * N
		minFromLeft = [float('inf')] * N
		for (i, ival) in reversed(list(enumerate(A))):
			if i == N - 1:
				maxFromRignt[i] = ival
			else:
				maxFromRignt[i] = max(maxFromRignt[i + 1], ival)
		for (i, ival) in enumerate(A):
			if i == 0:
				minFromLeft[i] = ival
			else:
				minFromLeft[i] = min(minFromLeft[i - 1], ival)
		i = 0
		j = 0
		maxDiff = -1
		while i < N and j < N:
			if minFromLeft[i] <= maxFromRignt[j]:
				maxDiff = max(maxDiff, j - i)
				j += 1
			else:
				i += 1
		return maxDiff


class Solution:

	def maxIndexDiff(self, a, n):
		l = [0 for i in range(n)]
		l[n - 1] = a[n - 1]
		for i in range(n - 2, -1, -1):
			l[i] = max(l[i + 1], a[i])
		i = 0
		j = 0
		mx = 0
		while i < n and j < n:
			if a[i] <= l[j]:
				mx = max(mx, j - i)
				j = j + 1
			else:
				i = i + 1
		return mx


class Solution:

	def maxIndexDiff(self, A, N):
		min_ele = 200000000
		minArr = []
		for i in range(N):
			if min_ele > A[i]:
				min_ele = A[i]
			minArr.append(min_ele)
		B = A[::-1]
		max_ele = -1
		maxArr = []
		for i in range(N):
			if max_ele < B[i]:
				max_ele = B[i]
			maxArr.append(max_ele)
		maxArr = maxArr[::-1]
		max_diff = 0
		i = 0
		j = 0
		while i <= j and i < N and (j < N):
			while j < N and minArr[i] <= maxArr[j]:
				j += 1
			j -= 1
			if i == j:
				i += 1
				j += 1
				continue
			max_diff = max(max_diff, j - i)
			if j == N - 1:
				break
			i += 1
		return max_diff