Given an array A of integers, a ramp is a tuple (i, j) for which i < j and A[i] <= A[j].  The width of such a ramp is j - i.
Find the maximum width of a ramp in A.  If one doesn't exist, return 0.
 
Example 1:
Input: [6,0,8,2,1,5]
Output: 4
Explanation: 
The maximum width ramp is achieved at (i, j) = (1, 5): A[1] = 0 and A[5] = 5.


Example 2:
Input: [9,8,1,0,1,9,4,0,4,1]
Output: 7
Explanation: 
The maximum width ramp is achieved at (i, j) = (2, 9): A[2] = 1 and A[9] = 1.




 
Note:

2 <= A.length <= 50000
0 <= A[i] <= 50000

Difficulty: interview

Starter code:

class Solution:
    def maxWidthRamp(self, A: List[int]) -> int:
        

Solutions:
class Solution:
    def maxWidthRamp(self, A: List[int]) -> int:
        width = 0
        icandidate = [0]
        for i in range(len(A)):
            if A[i] < A[icandidate[-1]]:
                icandidate.append(i)
        for j in range(len(A) - 1, -1, -1):
            while icandidate and A[icandidate[-1]] <= A[j]:
                width = max(width, j - icandidate.pop())
        return width

class Solution:
    def maxWidthRamp(self, A: List[int]) -> int:
        stack = []
        n = len(A)
        for i in range(n):
            if not stack or A[stack[-1]] > A[i]:
                stack.append(i)
        
        res = 0
        i = n-1
        while i > res:
            while stack and A[stack[-1]] <= A[i]:
                res = max(res, i-stack[-1])
                stack.pop()
            i -= 1
        return res

class Solution:
    def maxWidthRamp(self, A: List[int]) -> int:
        sorted_indices = sorted(list(range(len(A))), key=lambda x: A[x])
        minimum_index = sorted_indices[0]
        answer = 0
        
        for i in range(1, len(sorted_indices)):
            if sorted_indices[i] > minimum_index:
                answer = max(answer, sorted_indices[i] - minimum_index)
            else:
                minimum_index = sorted_indices[i]
        
        return answer
            


class Solution:
    def maxWidthRamp(self, A: List[int]) -> int:
        n = len(A)
        idx = sorted(range(n), key=A.__getitem__)
        i = n
        result = 0
        for j in idx:
            result = max(result, j - i)
            i = min(i, j)
        return result

class Solution:
    def maxWidthRamp(self, A: List[int]) -> int:
        idxs = sorted(range(len(A)), key=lambda i: A[i])

        ramp = 0
        mini = len(A)
        for idx in idxs:
            mini = min(mini, idx)
            ramp = max(ramp, idx-mini)
        return ramp

class Solution:
    def maxWidthRamp(self, A: List[int]) -> int:
        stack, ret = [], 0
        for i, a in enumerate(A):
            if not stack or A[stack[-1]] > a: stack.append(i)
        for i in reversed(range(len(A))):
            while stack and A[stack[-1]] <= A[i]:
                ret = max(ret, i - stack.pop())
        return ret

class Solution:
    def maxWidthRamp(self, A: List[int]) -> int:
        a = sorted(list(range(len(A))), key=lambda x: A[x])
        ans = 0
        m = float('inf')
        for i in a:
            ans = max(ans, i-m)
            m = min(m, i)
        return ans
            
            


class Solution:
    def maxWidthRamp(self, A: List[int]) -> int:
        n = len(A)
        rightMax = [0 for i in range(n+1)]
        
        for i in range(n-1, -1, -1):
            rightMax[i] = max(rightMax[i+1], A[i])
        
        i = 0
        j = 0
        result = 0
        
        while i < n and j < n:
            if A[i] <= rightMax[j]:
                result = max(result, j - i)
                j += 1
            else:
                i += 1
        return result

from operator import itemgetter
class Solution:
    def maxWidthRamp(self, A: List[int]) -> int:
        B = [(i,A[i]) for i in range(0,len(A))]
        B.sort(key=itemgetter(1))
        
        curminidx = B[0][0]
        res = 0
        for i in range(1, len(A)):
            curidx = B[i][0]
            if curidx<curminidx:
                curminidx = curidx
            else:
                res = max(res, curidx-curminidx)
                
        return res

class Solution:
    def maxWidthRamp(self, A: List[int]) -> int:
        n  = len(A)
        stack = []
        for i in range(n):
            if not stack or A[stack[-1]] >= A[i]:
                stack.append(i)
        
        res = 0
        for i in range(n - 1, -1, -1):
            while stack and A[stack[-1]] <= A[i]:
                res = max(res, i - stack.pop())
                
        return res

class Solution:
    def maxWidthRamp(self, A: List[int]) -> int:
        st_i = [a for a, _ in sorted(enumerate(A), key=lambda a: a[-1])]

        mi = math.inf
        mx =   -math.inf

        for idx in st_i:
            mi = min(idx,  mi)
            mx = max(mx, idx - mi)

        return mx


class Solution(object):
    def maxWidthRamp(self, A):
        ans = 0
        m = float('inf')
        for i in sorted(range(len(A)), key = A.__getitem__):
            ans = max(ans, i - m)
            m = min(m, i)
        return ans

class Solution:
    def maxWidthRamp(self, A: List[int]) -> int:
        largest = 0
        
        A = [(index, value) for index, value in enumerate(A)]
        
        A.sort(key=lambda x: x[1])
        
        minimum = float('inf')
        for index, el in A:
            largest = max(largest, index - minimum)
            minimum = min(index, minimum)
                    
        return largest
                


class Solution:
    def maxWidthRamp(self, A: List[int]) -> int:
        #stack maintains the index of strictly descending numbers
        stack = []
        for i,v in enumerate(A):
            if i==0 or v<A[stack[-1]]:
                stack.append(i)
        ans = 0
        for i in range(len(A)-1,-1,-1):
            #if A[i]<A[stack[-1]], then it must be smaller than all
            #the prev elements in stack, 
            #since stack is increasing (by popping)
            
            #then wait until larger elements
            #maybe we can find longer ramp
            while stack and A[i]>=A[stack[-1]]:
                ans = max(ans,i-stack.pop())
        return ans

class Solution:
    def maxWidthRamp(self, A):
        sorted_idx = [x[0] for x in sorted(enumerate(A), key=lambda x: x[1])]
        res = 0
        min_idx = sorted_idx[0]
        for idx in sorted_idx:
            res = max(res, idx - min_idx)
            min_idx = min(min_idx, idx)
        return res

class Solution:
    def maxWidthRamp(self, A: List[int]) -> int:
        # sorting sol O(nlgn)
        arr = [(a,i) for i, a in enumerate(A)]
        arr.sort()
        imin, res = float('inf'), 0
        for _, i in arr:
            res = max(res, i-imin)
            imin = min(imin, i)
        return res
        


class Solution:
    def maxWidthRamp(self, A: List[int]) -> int:
        stack = []
        
        for i, val in enumerate(A):
            if not stack or val < A[stack[-1]]:
                stack.append(i)
                
        maxWidth = 0
        
        for i in range(len(A)-1, -1, -1):
            val = A[i]
            while stack and val >= A[stack[-1]]:
                maxWidth = max(maxWidth, i - stack.pop())
            
        return maxWidth


class Solution:
    def maxWidthRamp(self, A: List[int]) -> int:
        # sorting sol O(nlgn)
        arr = [(a,i) for i, a in enumerate(A)]
        arr.sort()
        # # first way is keep imin, start from left of arr
        # imin, res = float('inf'), 0
        # for _, i in arr:
        #     res = max(res, i-imin)
        #     imin = min(imin, i)
        # return res
        
        # second way is keep imax, start from right of arr
        imax, res = float('-inf'), 0
        for _, i in reversed(arr):
            res = max(res, imax-i)
            imax = max(imax, i)
        return res
        


class Solution:
    def maxWidthRamp(self, A: List[int]) -> int:
        n = len(A)
        arr = sorted([(a,i) for i, a in enumerate(A)])
        rindex = [0] * n
        rindex[-1] = arr[-1][1]
        for i in range(n-2, -1, -1):
            rindex[i] = max(arr[i][1], rindex[i+1])
        mx = 0
        for i in range(n):
            mx = max(mx, rindex[i]-arr[i][1])
        return mx

class Solution:
    def maxWidthRamp(self, A: List[int]) -> int:
        stack = []
        
        for i, val in enumerate(A):
            if not stack or val < A[stack[-1]]:
                stack.append(i)
                
        maxWidth = 0
        
        for i in range(len(A)-1, -1, -1):
            val = A[i]
            while stack and val >= A[stack[-1]]:
                maxWidth = max(maxWidth, i - stack.pop())
            
        return maxWidth

class Solution:
    def maxWidthRamp(self, A: List[int]) -> int:
        ans = {}
        for i in range(len(A)):
            if A[i] in list(ans.keys()):
                ans[A[i]].append(i)
            else:
                ans[A[i]]=[i]
                
        B=sorted(A,reverse=True)
        #print(B)
        max_index = -1
        ramp=0
        for key in B:
            
            l = max_index-ans[key][0]
            ramp = max(ramp,l)
            max_index = max(max_index,ans[key][len(ans[key])-1])
        
        return ramp


class Solution:
    def maxWidthRamp(self, A: List[int]) -> int:
        ans = 0
                
        l = [(n, i) for i, n in enumerate(A)]
    
        l.sort()
        
        mini = float('inf')
        
        for e in l:
            mini = min(mini, e[1])
            ans = max(ans, e[1] - mini)
        return ans
            
        


class Solution:
    def maxWidthRamp(self, A: List[int]) -> int:
        # decreasing stack
        stack = []
        for i,a in enumerate(A):
            if not stack or a<A[stack[-1]]:
                stack.append(i)
        ans = 0
        for i in range(len(A)-1,-1,-1):
            while stack and A[stack[-1]]<=A[i]:
                ans = max(ans, i-stack[-1])
                stack.pop()
        return ans

class Solution:
    def maxWidthRamp(self, A: List[int]) -> int:
        A_idx = []
        for idx, a in enumerate(A):
            A_idx.append((a, idx))
            
        A_idx_sorted = sorted(A_idx, key = lambda x: x[0])
        
        mn = float('inf')
        res = 0
        for a, idx in A_idx_sorted:
            res = max(res, idx - mn)
            mn = min(mn, idx)
        return res


class Solution:
    def maxWidthRamp(self, A: List[int]) -> int:
        val_pos_list = [(value, pos) for pos, value in enumerate(A)]
        val_pos_list.sort()
        rightmost = len(A) - 1
        visited_pos = set()
        result = 0
        
        for value, pos in val_pos_list:
            while rightmost in visited_pos:
                rightmost -= 1
            distance = max(0, rightmost - pos)
            result = max(result, distance)
            visited_pos.add(pos)
        
        return result


class Solution:
    def maxWidthRamp(self, A: List[int]) -> int:
        n = len(A)
        minLeft, maxRight = [A[0]] * n, [A[-1]] * n
        for i in range(1, n):
            minLeft[i] = min(minLeft[i - 1], A[i])
            maxRight[n - i - 1] = max(maxRight[n - i], A[n - i - 1])
        i = j = n - 1
        res = 0
        while i >= 0 and j >= 0:
            if minLeft[i] <= maxRight[j]:
                res = max(res, j - i)
                i -= 1
            else:
                j -= 1
        return res

class Solution:
    def maxWidthRamp(self, A: List[int]) -> int:
        res = 0
        m = float('inf')
        for i in sorted(list(range(len(A))), key=lambda x: A[x]):
            res = max(res, i - m)
            m = min(m, i)
        return res


class Solution:
    def find_right_max(self,arr):
        right_max = [arr[-1]] 
        for i in range(len(arr)-2,-1,-1): 
            right_max.append(max(arr[i],right_max[-1]))
            
        return reversed(right_max)
    
    def maxWidthRamp(self, A: List[int]) -> int:
        indices_sort =  [i[0] for i in sorted(enumerate(A), key=lambda x:x[1])]
        set_ele = set(A) 
        indices = [] 
        for idx in indices_sort:
            if idx in set_ele: 
                indices.append(idx)
                
        
        right_max = self.find_right_max(indices_sort)
        max_width_ramp = float('-inf')
        for idx,right_max in zip(indices_sort, right_max): 
            max_width_ramp = max(right_max - idx, max_width_ramp)
            
        return max_width_ramp
    


class Solution:
    def maxWidthRamp(self, A: List[int]) -> int:
        # result = 0
        # for i in range(len(A)):
        #     for j in range(i+1,len(A)):
        #         if A[i]<=A[j]:
        #             result = max(result,j-i)
        # return result
        # Brute Force, Time Limit Exceeded
        
        # two pointer
#         rMax = [0]*len(A)
#         rMax[-1] = A[-1]
#         for i in range(len(A)-1)[::-1]:
#             rMax[i] = max(rMax[i+1],A[i])        
#         L=R=0
#         result=0
        
#         while R<len(A):
#             while L<R and A[L]>rMax[R]:
#                 L+=1
#             result = max(result,R-L)
#             R+=1
#         return result

        Aindex = [(a,i) for i,a in enumerate(A)]
        Aindex.sort(key=lambda x:(x[0],x[1]))
        mn=len(A)
        ans=0
        for a,i in Aindex:
            ans=max(ans,i-mn)
            mn=min(mn,i)
        return ans
        


        # stack = []
        # res = 0
        # for i in range(len(A))[::-1]:
        #     #print(i,stack)
        #     if not stack or A[i] > stack[-1][0]:
        #         stack.append([A[i], i])
        #     else:
        #         j = stack[bisect.bisect(stack, [A[i], i])][1]
        #         print(stack,[A[i], i],bisect.bisect(stack, [A[i], i]),j)
        #         res = max(res, j - i)
        # return res
    
        # s = []
        # res = 0
        # for i, a in enumerate(A):
        #     if not s or A[s[-1]] > a:
        #         s.append(i)
        # print(s)
        # for j in range(len(A))[::-1]:
        #     while s and A[s[-1]] <= A[j]:
        #         res = max(res, j - s.pop())
        # return res


class Solution:
    def maxWidthRamp(self, A: List[int]) -> int:
        collections = {}

        for i, el in enumerate(A):
            if el in collections:
                collections[el][1] = i
            else:
                collections[el] = [i, i]

        sorted_collections = sorted(collections.keys())
        for i in range(1, len(sorted_collections)):
            left, right = i, len(sorted_collections) - i - 1

            collections[sorted_collections[left]][0] = min(collections[sorted_collections[left]][0], collections[sorted_collections[left - 1]][0])
            collections[sorted_collections[right]][1] = max(collections[sorted_collections[right]][1], collections[sorted_collections[right + 1]][1])

        result = 0
        for el in collections.values():
            result = max(result, el[1] - el[0])
        return result

class Solution:
    def maxWidthRamp(self, A: List[int]) -> int:
        ind = [i for i in range(len(A))]
        A, ind = zip(*sorted(zip(A, ind)))
        m = len(A)-1
        ans = 0
        for i in range(len(A)):
            ans = max(ind[i] - m, ans)
            m = min(ind[i], m)
        return ans

class Solution:
    def maxWidthRamp(self, A: List[int]) -> int:
        minHeap = [(A[i], i) for i in range(len(A))]
        heapq.heapify(minHeap)
        maxWidth = 0
        minVal, minPos = heapq.heappop(minHeap)
        
        while minHeap:
            val, pos = heapq.heappop(minHeap)
            if val >= minVal:
                maxWidth = max(maxWidth, pos - minPos)
            if pos < minPos:
                minVal = val
                minPos = pos
        
        return maxWidth

class Solution:
    def maxWidthRamp(self, A: List[int]) -> int:
        n  = len(A)
        stack = []
        for i in range(n):
            if not stack or A[stack[-1]] > A[i]:
                stack.append(i)
        
        res = 0
        for i in range(n - 1, -1, -1):
            while stack and A[stack[-1]] <= A[i]:
                res = max(res, i - stack.pop())
                
        return res

class Solution:
    def maxWidthRamp(self, A: List[int]) -> int:
        left = [A[0],]
        right = [A[-1],]
        for i in range(1,len(A)):
            left.append(min(A[i],left[i-1]))
            right.append(max(A[len(A)-1-i],right[-1]))
        right = right[::-1]
        pt_l = 0
        pt_r = 0
        ans = 0
        while pt_r <len(A):
            if left[pt_l]<=right[pt_r]:
                ans = max(ans,pt_r - pt_l)
                pt_r+=1
            else:
                pt_l +=1
        return ans

class Solution:
    def maxWidthRamp(self, A: List[int]) -> int:
        # stack + binary search
        descends = [(A[0], 0)]
        def bs(t):
            lo, hi = 0, len(descends) - 1
            while lo < hi:
                mid = (lo + hi) // 2
                if descends[mid] > t:
                    lo = mid + 1
                else:
                    hi = mid
            return lo
        rint = 0
        for i in range(1, len(A)):
            if A[i] < descends[-1][0]:
                descends.append((A[i], i))
            else:
                left = bs((A[i], i))
                # print(i, left, descends[left][1], descends)
                rint = max(rint, i - descends[left][1])
        return rint

class Solution:
    def maxWidthRamp(self, A: List[int]) -> int:
        s = []
        
        for i in range(len(A)):
            if(not s or A[s[-1]] > A[i]):
                s.append(i)
        
        j = len(A)-1
        res = 0
        while(j > res):
            while(s and A[j] >= A[s[-1]]):
                i = s.pop()
                res = max(res, j-i)
            j -= 1
        return res

class Solution:
    def maxWidthRamp(self, A: List[int]) -> int:
        # Track index of min from left
        idxsMin, res = [], 0
        for i, x in enumerate(A):
            if not idxsMin or A[idxsMin[-1]] > x:
                idxsMin.append(i)
        # Compare every element from right with the min element from left
        for j in range(len(A))[::-1]:
            while idxsMin and A[idxsMin[-1]] <= A[j]:
                res = max(res, j - idxsMin.pop())
        return res

class Solution:
    def maxWidthRamp(self, A: List[int]) -> int:
        n = len(A)
        l = []
        res = 0
        for j in range(n):
            if not l or A[l[-1]] > A[j]:
                l.append(j)
            else:
                left, right = 0, len(l) - 1
                while left < right:
                    mid = (left + right) // 2
                    if A[l[mid]] <= A[j]:
                        right = mid
                    else:
                        left = mid + 1
                res = max(res, j - l[left])
        return res


class Solution:
    def maxWidthRamp(self, A: List[int]) -> int:
        # ans = 0
        # m = float('inf')
        # for i in sorted(range(len(A)), key = A.__getitem__):
        #     m = min(i, m)
        #     ans = max(ans, i - m)
        # return ans
        stack = []
        # A.append(float('inf'))
        ans = 0
        for i, a in enumerate(A):
            if (not stack) or stack[-1][0] > a:
                stack.append((a, i))
            else:
                l, r = 0, len(stack) - 1
                while l < r:
                    # print(l, r)
                    m = (r + l) // 2
                    if stack[m][0] > a:
                        l = m + 1
                    else:
                        r = m
                    
                if stack[l][0] <= a:
                    ans = max(ans, i - stack[l][1])
            # print(stack, ans)
        return ans
                        
                        
                    
       
        



class Solution:
    def maxWidthRamp(self, A: List[int]) -> int:
        stack = []
        res = 0
        for i, num in enumerate(A):
            if not stack or A[stack[-1]] > num:
                stack.append(i)
        for j in range(len(A) - 1, -1, -1):
            while stack and A[stack[-1]] <= A[j]:
                res = max(res, j - stack.pop())
        return res

class Solution:
    def maxWidthRamp(self, x: List[int]) -> int:
        ma=0
        l=len(x)
        st=[(x[0],0)]
        for i in range(l):
            if x[i]<st[-1][0]:
                st.append((x[i],i))
        for i in range(l-1,-1,-1):
            while st!=[] and x[i]>=st[-1][0]:
                a,b= st.pop(-1)
                ma=max(i-b,ma)
            if st==[]:break
        return ma


class Solution:
    def maxWidthRamp(self, A: List[int]) -> int:
        n = len(A)
        
        stack = []
        for i, num in enumerate(A):
            if not stack or num < A[stack[-1]]:
                stack.append(i)
                
        ans = 0
        for j in range(n-1, -1, -1):
            while stack and A[j] >= A[stack[-1]]:
                ans = max(ans, j - stack.pop())
        return ans

class Solution:
    def maxWidthRamp(self, A: List[int]) -> int:
        mx=0
        ind=float('inf')
        index=collections.defaultdict(list)
        
        for i,x in enumerate(A):
            index[x].append(i)
        print(index)
        for num in sorted(A):
            mx=max(mx,index[num][-1]-ind)
            ind=min(ind,index[num][0])
        return mx


class Solution:
    def maxWidthRamp(self, A: List[int]) -> int:
        stack = []
        res = 0
        for i, a in enumerate(A):
            if stack and A[stack[-1]]<=a:
                j = len(stack)-1
                
                while j>=0 and A[stack[j]]<=a:
                    # print(i, a, j, stack, A[stack[j]])
                    res = max(res, i-stack[j])
                    j -= 1
            else:
                stack.append(i)
                
        return res

class Solution:
    def maxWidthRamp(self, A: List[int]) -> int:
        # 第一遍傻傻 两次循环TLE
        # 还是应该用stack, 单调递减栈 小的入栈
        
        res = 0
        stack = []
        for i, a in enumerate(A):
            if not stack or stack[-1][1] > a: # 小于才入栈， 相等就可以取res了
                stack.append((i,a))
            else:
                N = len(stack) -1  # 要遍历每一个入stack的
                while N >= 0 and stack[N][1]<= a:
                    res = max(res,i-stack[N][0])
                    N = N -1
                    
        return res


class Solution:
    def maxWidthRamp(self, A: List[int]) -> int:
        stack=[]
        res=0
        for i,a in enumerate(A):
            if not stack or stack[-1][1]>a:
                stack.append([i,a])
            else:
                j=len(stack)-1
                while j>=0 and stack[j][1]<=a:
                    res=max(res,i-stack[j][0])
                    j-=1
        return res

class Solution:
    def maxWidthRamp(self, A: List[int]) -> int:
        # 第一遍傻傻 两次循环TLE
        # 还是应该用stack, 单调递减栈 小的入栈
        
        res = 0
        stack = []
        for i, a in enumerate(A):
            if not stack or stack[-1][1] > a: # 小于才入栈， 相等就可以取res了
                stack.append((i,a))
            else:
                N = len(stack) -1 
                while N >= 0 and stack[N][1]<= a:
                    res = max(res,i-stack[N][0])
                    N = N -1
                    
        return res


class Solution:
    def maxWidthRamp(self, A: List[int]) -> int:
        record = [[A[i], i] for i in range(len(A))]
        record.sort(key = lambda x:[x[0], x[1]])
        res = 0
        pre_min = record[0][1]
        for i in range(1,len(A)):
            pre_min = min(pre_min, record[i][1])
            res = max(res, record[i][1]-pre_min)
        return res

class Solution:
    def maxWidthRamp(self, A: List[int]) -> int:
        # https://blog.csdn.net/fuxuemingzhu/article/details/85223568
        N = len(A)
        stack = []
        res = 0
        for i, a in enumerate(A):
            if not stack or stack[-1][1] > a:
                stack.append((i, a))
            else:
                x = len(stack) - 1
                while x >= 0 and stack[x][1] <= a:
                    res = max(res, i - stack[x][0])
                    x -= 1
        return res

class Solution:
    def maxWidthRamp(self, A: List[int]) -> int:
        N = 50001
        sms = [None] * N
        lgs = [None] * N

        for i, x in enumerate(A):
            if sms[x] is None:
                sms[x] = i
            lgs[x] = i

        m = 0
        ss = float('inf')
        for x in range(N):
            if lgs[x] is None:
                continue
            ss = min(ss, sms[x])
            m = max(m, lgs[x] - ss)

        return m

class Solution:
    def maxWidthRamp(self, A: List[int]) -> int:
        stack = []
        #prev = float('inf')
        for i,v in enumerate(A):
            if i==0 or v<A[stack[-1]]:
                stack.append(i)
        
        ans = 0
        #print(stack)
        for j in range(len(A)-1,-1,-1):
            i = j
            while stack and A[j]>=A[stack[-1]]:
                i = stack.pop()
            
            ans = max(ans,j-i)
        return ans    

class Solution:
    def maxWidthRamp(self, A: List[int]) -> int:
        stack, ans = [], 0
        for i, val in enumerate(A):
            if not stack or A[stack[-1]] > val:
                stack.append(i)
        for j in reversed(list(range(len(A)))):
            while stack and A[stack[-1]] <= A[j]:
                ans = max(ans, j-stack.pop())
        return ans


class Solution:
    def maxWidthRamp(self, A: List[int]) -> int:
        numbers = list((num, i) for i, num in enumerate(A))
        numbers.sort()
        
        max_gap = 0
        min_element = numbers[0][1]
        
        for i in range(1, len(A)):
            min_element = min(min_element, numbers[i][1])
            max_gap = max(max_gap, numbers[i][1] - min_element)
        
        return max_gap

class Solution:
    def maxWidthRamp(self, a: List[int]) -> int:
        sis = sorted(list(range(len(a))), key=a.__getitem__)
        return max(i - m for m, i in zip(itertools.accumulate(sis, min), sis))
        


class Solution:
    def maxWidthRamp(self, A: List[int]) -> int:
        #11M coding start
        
        min_map, max_map = {}, {}
        
        for i, v in enumerate(A):
            min_map[v] = min(i, min_map.get(v, i))
            max_map[v] = max(i, max_map.get(v, i))
        
        min_idx = None
        res = 0
        for i in range(0, 50001):
            if i not in min_map:
                continue
            
            if min_idx is None:
                min_idx = min_map[i]
            else:
                min_idx = min(min_idx, min_map[i])

            if max_map[i] > min_idx:
                res = max(res, max_map[i] - min_idx)
                
        return res


class Solution:
    def maxWidthRamp(self, A: List[int]) -> int:
        # result = 0
        # for i in range(len(A)):
        #     for j in range(i+1,len(A)):
        #         if A[i]<=A[j]:
        #             result = max(result,j-i)
        # return result
        # Brute Force, Time Limit Exceeded
        
        # two pointer
#         rMax = [0]*len(A)
#         rMax[-1] = A[-1]
#         for i in range(len(A)-1)[::-1]:
#             rMax[i] = max(rMax[i+1],A[i])        
#         L=R=0
#         result=0
        
#         while R<len(A):
#             print(L,R,result)
#             while L<R and A[L]>rMax[R]:
#                 L+=1
#             result = max(result,R-L)
#             R+=1
            
#         return result

        Aindex = [(a,i) for i,a in enumerate(A)]
        Aindex.sort(key=lambda x:(x[0],x[1]))
        mn=len(A)
        ans=0
        for a,i in Aindex:
            print((i,ans,i-mn,mn))
            ans=max(ans,i-mn)
            mn=min(mn,i)
        return ans
        


        # stack = []
        # res = 0
        # for i in range(len(A))[::-1]:
        #     #print(i,stack)
        #     if not stack or A[i] > stack[-1][0]:
        #         stack.append([A[i], i])
        #     else:
        #         j = stack[bisect.bisect(stack, [A[i], i])][1]
        #         print(stack,[A[i], i],bisect.bisect(stack, [A[i], i]),j)
        #         res = max(res, j - i)
        # return res
    
        # s = []
        # res = 0
        # for i, a in enumerate(A):
        #     if not s or A[s[-1]] > a:
        #         s.append(i)
        # print(s)
        # for j in range(len(A))[::-1]:
        #     while s and A[s[-1]] <= A[j]:
        #         res = max(res, j - s.pop())
        # return res


class Solution:
    def maxWidthRamp(self, A: List[int]) -> int:
        
        helper=[]
        for i,x in enumerate(A):
            helper.append((x,i))
            
        helper.sort(key=lambda x:x[0])
        imin=helper[0][1]
        maxlen=0
        # print(helper)
        for val,indx in helper:
            if indx>=imin:
                maxlen=max(maxlen,indx-imin)
                
            imin=min(imin,indx)
            
        return maxlen
            
            
            
            
            


class Solution:
    def maxWidthRamp(self, A: List[int]) -> int:
        
        stack,n = [],len(A)
        maxy = 0
        i = 0
        for i,v in enumerate(A):
            if not stack or v<stack[-1][0]:
                stack.append((v,i))
                continue
            
            j = -1
            while j>=-1*len(stack) and v>=stack[j][0]:
                maxy = max(maxy, i-stack[j][1])
                j-=1
            
                
        return maxy

class Solution:
    def maxWidthRamp(self, A: List[int]) -> int:
        mx=0
        ind=float('inf')
        index=collections.defaultdict(list)
        for i, x in enumerate(A):
            index[x].append(i)
            
        for i in sorted(A):
            mx=max(mx,index[i][-1]-ind)
            ind=min(ind,index[i][0])
        return mx


class Solution:
    def maxWidthRamp(self, A: List[int]) -> int:
        preList = [0]
        ALen = len(A)
        for i in range(1, ALen):
            if A[i] < A[preList[-1]]:
                preList.append(i)
        # print(preList)
        ans = 0
        preR = len(preList)-1
        for i in range(ALen-1, -1, -1):
            l = 0
            while preR > 0 and preList[preR] >= i:
                preR -= 1
            r = preR
            # r = len(preList)-1
            if A[i] < A[preList[l]] and A[i] >= A[preList[r]]:
                while r > l:
                    # print(l, r)
                    m = (r+ l)//2
                    if A[preList[m]] < A[i]:
                        r = m
                    elif A[preList[m]] > A[i]:
                        l = m + 1
                    else:
                        l = m
                        r = m - 1
                # print(i, preList[l])
                ans = max(ans, i - preList[l])
            elif A[i] >= A[preList[l]]:
                ans = max(ans, i - preList[l])
                
        return ans


class Solution:
    def maxWidthRamp(self, A: List[int]) -> int:
        
        stack,n = [],len(A)
        maxy = 0
        i = 0
        for i,v in enumerate(A):
            if stack and maxy+stack[0][1]>=n: break
            if not stack or v<stack[-1][0]:
                stack.append((v,i))
                continue
            
            j = -1
            while j>=-1*len(stack) and v>=stack[j][0]:
                maxy = max(maxy, i-stack[j][1])
                j-=1
            
                
        return maxy

from sortedcontainers import SortedList

class Solution:
    def maxWidthRamp(self, A: List[int]) -> int:
        li = list()
        
        for i,n in enumerate(A):
            li.append((n,i))
            
        li.sort()
        
        ans = 0
        
        bt = SortedList()
        
        for pair in li:
            n = pair[0]
            i = pair[1]
            # print(bt)
            # print(i)
            if len(bt) == 0:
                bt.add(i)
                continue
            if bt[0] < i:
                if i - bt[0] > ans:
                    ans = i-bt[0]
            bt.add(i)
        
        return ans