Given an array A, partition it into two (contiguous) subarrays left and right so that:

Every element in left is less than or equal to every element in right.
left and right are non-empty.
left has the smallest possible size.

Return the length of left after such a partitioning.  It is guaranteed that such a partitioning exists.
 
Example 1:
Input: [5,0,3,8,6]
Output: 3
Explanation: left = [5,0,3], right = [8,6]


Example 2:
Input: [1,1,1,0,6,12]
Output: 4
Explanation: left = [1,1,1,0], right = [6,12]

 

Note:

2 <= A.length <= 30000
0 <= A[i] <= 10^6
It is guaranteed there is at least one way to partition A as described.

Difficulty: interview

Starter code:

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

Solutions:
class Solution:
    def partitionDisjoint(self, A: List[int]) -> int:
        biggest = A[0]
        newbiggest = A[0]
        lenL = 1
        total = 1
        for itr in A[1:]:
            total += 1
            if itr < biggest:
                lenL = total
                biggest = newbiggest
            else:
                if itr > newbiggest:
                    newbiggest = itr
        return lenL



class Solution:
    def partitionDisjoint(self, A: List[int]) -> int:
        res = 0
        v = A[0]
        max_sofar = v
        for i in range(len(A)):
            max_sofar = max(max_sofar, A[i])
            if A[i] < v:
                v = max_sofar
                res = i
                
        return res+1
    # 如果中间有一个数字变大，我不更新v， v只是之前最大的数
    # [32,57,24,19,0,24,49,67,87,87]  如果我不更新v，32 会一直最大，那么49 就归在右边了


class Solution:
    def partitionDisjoint(self, A: List[int]) -> int:
        a = [A[0]]
        b = [0 for i in range(len(A))]
        for i in range(1, len(A)):
            a.append(max(a[i - 1], A[i]))
        
        b[-1] = A[-1]
        for i in range(len(A) - 2, -1, -1):
            b[i] = min(b[i + 1], A[i])
            
        for i in range(len(A) - 1):
            if a[i] <= b[i + 1]:
                return i + 1
        return -1

class Solution:
    def partitionDisjoint(self, A: List[int]) -> int:
        n = len(A)
        mini = [float('-inf')]*n
        maxi = [float('inf')]*n
        mini[0] = A[0]
        maxi[n - 1] = A[n - 1]
        for i in range(1, n):
            mini[i] = max(mini[i - 1], A[i])
        
        for i in range(n-2, -1, -1):
            maxi[i] = min(maxi[i + 1], A[i])
        
        # print(mini)
        # print(maxi)
        for i in range(n - 1):
            if mini[i] <= maxi[i + 1]:
                return i + 1
        
        return 0

class Solution:
    def partitionDisjoint(self, A: List[int]) -> int:
        N = len(A)
        maxleft = [None] * N
        minright = [None] * N

        m = A[0]
        for i in range(N):
            m = max(m, A[i])
            maxleft[i] = m
        
        m = A[-1]
        for i in range(N -1, -1, -1):
            m = min(m, A[i])
            minright[i] = m
            
        for i in range(1, N):
            if maxleft[i-1] <= minright[i]:
                return i
            
            
#         # https://leetcode.com/problems/partition-array-into-disjoint-intervals/discuss/175904/Explained-Python-simple-O(N)-time-O(1)-space
        
#         # The idea is, v is nothing but the max value of the left half and max_so_far is a nonlocal maximum of the entire array. So by selecting elements only lesser than max of left side (v), we set V to the first element.
        
#         disjoint = 0
#         v = A[disjoint]
#         max_so_far = v
#         for i in range(len(A)):
#             max_so_far = max(max_so_far, A[i])
#             if A[i] < v: 
#                 disjoint = i
#                 v = max_so_far
#         return disjoint + 1


class Solution:
    def partitionDisjoint(self, A: List[int]) -> int:
        n = len(A)
        large = [0] * n
        small = [0] * n
        l, s = -sys.maxsize, sys.maxsize
        for i in range(n):
            l = max(l, A[i])
            s = min(s, A[n-1-i])
            large[i] = l
            small[n-1-i] = s
        for i in range(n):   
            if large[i] <= small[i+1]: return i+1
        return -1    


class Solution:
    def partitionDisjoint(self, A: List[int]) -> int:
        left = [A[0]]
        for i in range(1, len(A)):
            left.append(max(left[-1], A[i]))
        right = [A[-1]]
        for i in range(len(A) - 2, -1, -1):
            right.append(min(right[-1], A[i]))
        for i in range(1, len(A)):
            if left[i - 1] <= right[-i - 1]:
                return i
            


class Solution:
    def partitionDisjoint(self, A: List[int]) -> int:
        n = len(A)
        left = [0 for i in range(n)]
        right = [0 for i in range(n)]
        left[0], right[n-1] = A[0], A[n-1]
        for i in range(1, n):
            left[i] = max(left[i-1], A[i])
        for i in range(n-2, -1, -1):
            right[i] = min(right[i+1], A[i])
        print(left, right)
        for i in range(n-1):
            if left[i] <= right[i+1]:
                return i+1

class Solution:
    def partitionDisjoint(self, A: List[int]) -> int:
        run_max = [float('-inf')]
        run_min = [float('inf')]
        # get run_max
        p = 1
        while p < len(A):
            run_max.append(max(run_max[-1], A[p-1]))
            p += 1
        # get run_min
        p = len(A) - 2
        while p > -1:
            run_min.append(min(run_min[-1], A[p+1]))
            p -= 1
        run_min = run_min[::-1]
        
        # find the pos that satisfies the condition.
        res = -1
        p = 0
        done = False
        while p < len(A) - 1 and not done:
            if A[p] <= run_min[p] and run_max[p] <= run_min[p]:
                res = p + 1
                done = True
                
            p += 1
        return  res
    
    


class Solution:
    def partitionDisjoint(self, A: List[int]) -> int:
        left_max = []
        right_min = []
        for i in range(len(A)):
            if i == 0:
                left_max.append(A[i])
            else:
                left_max.append(max(A[i], left_max[-1]))
        for i in range(len(A)-1, -1, -1):
            if i == len(A) - 1:
                right_min.append(A[i])
            else:
                right_min.append(min(A[i], right_min[-1]))
        right_min.reverse()
        
        for i in range(len(A)-1):
            lm = left_max[i]
            rm = right_min[i+1]
            if lm <= rm:
                return i+1


class Solution:
    def partitionDisjoint(self, A: List[int]) -> int:
        n = len(A)
        max_left, min_right = [None]*n, [None]*n

        max_left[0] = A[0]
        for i in range(1, n):
            max_left[i] = max(max_left[i-1], A[i])

        min_right[-1] = A[-1]
        for i in range(n-2, -1, -1):
            min_right[i] = min(min_right[i+1], A[i])

        for i in range(1, n):
            if max_left[i-1] <= min_right[i]:
                return i

class Solution:
    def partitionDisjoint(self, A: List[int]) -> int:
        l, r = 0, len(A) - 1
        leftMax = A[l]
        rightMin = A[r]
        minHash = {}
        
        while l < r:
            leftMax = max(leftMax, A[l])
            rightMin = min(rightMin, A[r])
            
            if rightMin >= leftMax:
                r -= 1
            else:
                l += 1
        
        for i in range(r, len(A)):
            if A[i] not in minHash:
                minHash[A[i]] = []
            minHash[A[i]].append(i)
        minHash = sorted(list(minHash.items()), key=lambda x: x[0])
        
        #print (leftMax, rightMin, minHash)
        i, res = 0, 1
        while i < len(minHash) and minHash[i][0] < leftMax:
            positions = minHash[i][1]
            res = max(positions[-1]+1, res)
            i += 1

        return res


class Solution:
    def partitionDisjoint(self, A: List[int]) -> int:
        mx=[-1]*len(A)
        mn=[-1]*len(A)
        for i in range(len(A)):
            if i==0:
                mx[i]=A[i]
            else:
                mx[i]=max(A[i],mx[i-1])
        for j in range(len(A)-1,-1,-1):
            if j==len(A)-1:
                mn[j]=A[j]
            else:
                mn[j]=min(A[j],mn[j+1])
        #print(mx,mn)
        for i in range(len(A)-1):
            #print(mx[i],mn[i+1])
            if mx[i]<=mn[i+1]:
                #print('yo')
                return i+1
        return len(A)-1

class Solution:
    def partitionDisjoint(self, A: List[int]) -> int:
        n = len(A)
        memo = [[0 for _ in range(n)] for _ in range(2)]
        left, right = 0, (1<<31)-1
        i, j = 0, n-1
        while i < n and j >= 0:
            right = min(right, A[j])
            left = max(left, A[i])
            memo[0][i] = left
            memo[1][j] = right
            i += 1
            j -= 1
        i, j = 0, 1
        while j < n and memo[0][i] > memo[1][j]:
            i, j = i+1, j+1
        return j

from collections import Counter

class Solution:
    def partitionDisjoint(self, A: List[int]) -> int:
        
        c = Counter(A)
        d = Counter()
        
        keys = sorted(c.keys())
        
        d[keys[0]] = 0
        for i in range(1, len(keys)):
            d[keys[i]] = c[keys[i-1]] + d[keys[i-1]]
            
        lesscount, mx = 0, -float('inf')
        
        
        equal = 0
        
        for i in range(len(A)):
            # mx = max(mx, A[i])
            
            if A[i] < mx:
                lesscount += 1 
            elif A[i] == mx:
                equal += 1
            else:
                mx = A[i]
                lesscount += equal
                equal = 1
                

            # print(A[i], mx, lesscount, equal, d[mx])   
            if lesscount == d[mx]:
                return i + 1
            


class Solution:
    def partitionDisjoint(self, A: List[int]) -> int:
        left = [0 for i in range(len(A))]
        left[0] = A[0]
        for i in range(1, len(A)):
            left[i] = max(left[i-1], A[i])
        right = [0 for i in range(len(A))]
        right[-1] = A[-1]
        for i in reversed(range(len(A)-1)):
            right[i] = min(right[i+1], A[i])
        for i in range(len(A)-1):
            if left[i] <= right[i+1]:
                return i+1

class Solution:
    def partitionDisjoint(self, A: List[int]) -> int:
        N = len(A)
        maxLeft = dict()
        minRight = dict()
        
        if N == 2 and A[0] <= A[1]:
            return 1

        maxLeft[0] = A[0]
        for i in range(1, N - 1):
            maxLeft[i] = max(maxLeft[i - 1], A[i])
            
        minRight[N - 1] = A[-1]
        for i in range(N - 2, 0, -1):
            minRight[i] = min(minRight[i + 1], A[i])
            
        print({ 'maxLeft': maxLeft })
        print({ 'minRight': minRight })
        
        for i in range(N - 1):
            if maxLeft[i] <= minRight[i + 1]:
                return i + 1
            
        return -1

class Solution:
    def partitionDisjoint(self, A: List[int]) -> int:
        mx=[-1]*len(A)
        mn=[-1]*len(A)
        for i in range(len(A)):
            if i==0:
                mx[i]=A[i]
            else:
                mx[i]=max(A[i],mx[i-1])
        for j in range(len(A)-1,-1,-1):
            if j==len(A)-1:
                mn[j]=A[j]
            else:
                mn[j]=min(A[j],mn[j+1])
        #print(mx,mn)
        for i in range(len(A)-1):
            print(mx[i],mn[i+1])
            if mx[i]<=mn[i+1]:
                #print('yo')
                return i+1
        return len(A)-1

class Solution:
    def partitionDisjoint(self, A: List[int]) -> int:
        length = len(A)
        leftMax = A[0]
        currMax = leftMax
        ret = 0
        
        for i in range(1, length):
            currMax = max(A[i], currMax)
            if leftMax > A[i]:
                leftMax = currMax
                ret = i
        
        return ret + 1


class Solution:
    def partitionDisjoint(self, A: List[int]) -> int:
        maxval = A[0]
        v = A[0]
        disjoint = 0
        for i in range(len(A)):
            maxval = max(maxval,A[i])
            if A[i]<v:
                disjoint = i
                v = maxval
                
        return disjoint+1
                
        


class Solution:
    def partitionDisjoint(self, A: List[int]) -> int:
        split_index = 0
        local_max = A[0]
        max_num = local_max
        
        for i in range(len(A)):
            if A[i] < local_max:
                split_index = i
                local_max = max_num
            else:
                max_num = max(max_num,A[i])
        return split_index + 1

class Solution:
    def partitionDisjoint(self, A: List[int]) -> int:
        minA=[A[0],]
        for i in A[1:]:
            minA.append(max(i,minA[-1]))
        minB=[A[-1],]
        for i in A[:-1][::-1]:
            minB.append(min(minB[-1],i))
        minB=minB[::-1]
        for i in range(1,len(A)):
            if minA[i-1]<=minB[i]:
                return i


class Solution:
    def partitionDisjoint(self, A: List[int]) -> int:
        max_left = float('-inf')
        min_right = A[-1]
        left = []
        right = [A[-1]]
        
        for i in range(len(A)):
            max_left = max(max_left, A[i])
            left.append(max_left)
            
        for i in range(len(A) - 2, -1, -1):
            min_right = min(min_right, A[i + 1])
            right.append(min_right)
        right.reverse()
        #print(left)
        #print(right)
        for i in range(len(left)):
            if left[i] <= right[i]:
                return i + 1

class Solution:
    def partitionDisjoint(self, A: List[int]) -> int:
        left = [0]*len(A)
        for i in range(len(A)):
            if i == 0:
                left[i] = A[i]
            else:
                if A[i] > left[i-1]:
                    left[i] = A[i]
                else:
                    left[i] = left[i-1]
        
        A_reversed = A[::-1]
        right = [0]*len(A)
        for i in range(len(A)):
            if i == 0:
                right[i] = A_reversed[i]
            else:
                if A_reversed[i] < right[i-1]:
                    right[i] = A_reversed[i]
                else:
                    right[i] = right[i-1]
        right = right[::-1]
        
        print(left, right)
        for i in range(len(left)-1):
            if left[i] <= right[i+1]:
                return i+1

class Solution:
    def partitionDisjoint(self, A: List[int]) -> int:
        n = len(A)
        d = [0] * n
        d[n-1] = A[n-1]
        for i in range(len(A)-2,-1,-1):
            d[i] = min(A[i],d[i+1])
        # print(d)
        mx = A[0]
        for i in range(1,n):
            if mx <= d[i]:
                return i
            else:
                mx = max(mx,A[i])
            


class Solution:
    def partitionDisjoint(self, A: List[int]) -> int:
        least = [float('inf')] * len(A)
        for i in range(len(A)-1, -1, -1):
            if i == len(A) - 1:
                least[i] = A[i]
            else:
                least[i] = min(least[i+1], A[i])
        greatest = A[0]    
        for i in range(1, len(A)):
            if greatest <= least[i]:
                break
            greatest = max(greatest, A[i])
        return i


class Solution:
    def partitionDisjoint(self, A: List[int]) -> int:
        l = [0] * len(A)
        r = [0] * len(A)
        
        for i in range(len(l)):
            l[i] = max(A[i],l[i-1])
        r[-1] = A[-1]
        for i in range(len(r)-2,-1,-1):
            r[i] = min(A[i],r[i+1])
            
        print(l)
        print(r)
        for i in range(len(l)):
            if l[i] <= r[i+1]:
                return i+1
        return len(l)

class Solution:
    def partitionDisjoint(self, A: List[int]) -> int:
        ans = 1
        all_max = A[0]
        curr_max = 0
        for i in range(len(A)):
            curr_max = max(curr_max, A[i])
            if all_max > A[i]:
                all_max = curr_max
                ans = i + 1
        return ans

class Solution:
    def partitionDisjoint(self, A: List[int]) -> int:
        '''
        [5,0,3,8,6]
         mn=[5,0,0,0]
         mx=[5,5,5,8,8]
        
        [1,1,1,0,6,12]
        mx=[1,1,1,1,6,12]
        '''
        ml=0
        mx=-1e9
        mxsofar=1e9
        for i,a in enumerate(A):
            mx=max(a,mx)
            if a<mxsofar:
                ml=i+1
                mxsofar=mx
                #print(\"a=%d,mx=%d,mxsofar %d\"%(a,mx,mxsofar))
            
        return ml

class Solution:
    def partitionDisjoint(self, A: List[int]) -> int:
        right = 1
        maxLeft = A[0]
        
        sortedRight = sorted(range(right, len(A)), key=lambda k: A[k])
        
        while A[sortedRight[0]] < maxLeft:
            right = sortedRight[0] + 1
            maxLeft = max(A[:right])
            sortedRight = sorted(range(right, len(A)), key=lambda k: A[k])
        
        return right

class Solution:
    def partitionDisjoint(self, A: List[int]) -> int:
        left = [0]*len(A)
        left[0] = A[0]
        for i in range(1,len(A)):
            left[i] = max(A[i],left[i-1])
        right = [0]*len(A)
        right[-1] = A[-1]
        for i in range(len(A)-2,-1,-1):
            right[i] = min(A[i],right[i+1])
        print((*left))
        print((*right))
        for i in range(1, len(A)):
            if right[i] >= left[i-1]:
                return i
        
#         N = len(A)
#         maxleft = [None] * N
#         minright = [None] * N

#         m = A[0]
#         for i in range(N):
#             m = max(m, A[i])
#             maxleft[i] = m

#         m = A[-1]
#         for i in range(N-1, -1, -1):
#             m = min(m, A[i])
#             minright[i] = m
#         print(*maxleft)
#         print(*minright)
#         for i in range(1, N):
#             if maxleft[i-1] <= minright[i]:
#                 return i


class Solution:
    def partitionDisjoint(self, A: List[int]) -> int:
        # O(N**2) with sapce O(1)
        n = len(A)
        
            
            
        # O(n) with space O(n)
        m = n - 1
        left_max = [0] * m
        left_max[0] = A[0]
        right_min = [0] * m
        right_min[-1] = A[-1]
        
        for i in range(1,n-1):
            left_max[i] = max(left_max[i-1], A[i])
        
        
        for i in reversed(range(1,m)):
            right_min[i-1] = min(right_min[i], A[i])
        for i in range(m):
            if left_max[i] <= right_min[i]:
                return i + 1

class Solution:
    def partitionDisjoint(self, A: List[int]) -> int:
        # O(N**2) with sapce O(1)
        n = len(A)
        
            
            
        # O(n) with space O(n)
        m = n - 1
        left_max = [0] * m
        left_max[0] = A[0]
        right_min = [0] * m
        right_min[-1] = A[-1]
        
        for i in range(1,n-1):
            left_max[i] = max(left_max[i-1], A[i])
        
        
        for i in reversed(range(1,m)):
            right_min[i-1] = min(right_min[i], A[i])
        
        print(left_max)
        print(right_min)
        for i in range(m):
            if left_max[i] <= right_min[i]:
                return i + 1

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

        bound = r = 0
        gmax = lmax = A[0]
        while r < len(A):
            if A[r] >= gmax:
                lmax = max(lmax, A[r])
                r += 1
            else:
                bound = r
                gmax = max(gmax, lmax)
                r += 1

        return bound+1


class Solution:
    def partitionDisjoint(self, A: List[int]) -> int:
        h = {}
        right = float('inf')

        for j in range(len(A)-1,-1,-1):
            right = min(right, A[j])
            h[j] = right
        
        left = float('-inf')
        for i in range(len(A)-1):
            left = max(left, A[i])
            if left <= h[i+1]:
                return i + 1
        


class Solution:
    def partitionDisjoint(self, A: List[int]) -> int:
        cnt = collections.Counter(A)
        cur = 0
        minn = min(cnt.keys())
        for i in range(len(A)):
            cur = max(cur, A[i])
            cnt[A[i]] -= 1
            if cnt[A[i]] == 0:
                del cnt[A[i]]
                if minn == A[i]:
                    minn = min(cnt.keys())
            if minn >= cur:
                return i + 1


class Solution:
    def partitionDisjoint(self, A: List[int]) -> int:
        l = [A[0]]
        r = [A[-1]]

        for i, v in enumerate(A):
            if i == 0:
                continue

            l.append(max(l[i-1], A[i]))
            r.append(min(r[i-1], A[len(A) - i - 1]))

        r.reverse()
        for i in range(1, len(l)):
            if l[i-1] <= r[i]:
                return i

class Solution:
    def partitionDisjoint(self, A: List[int]) -> int:
        n = len(A)
        
        partidx = 0
        left_max = A[0]
        seen_max = A[0]
        for i in range(1, n):
            seen_max = max(seen_max, A[i])
            if A[i] < left_max:
                partidx = i
                left_max = seen_max
        return partidx + 1
            
        
        
        
        # left = [0 for i in range(n)]
        # right = [0 for i in range(n)]
        # left[0], right[n-1] = A[0], A[n-1]
        # for i in range(1, n):
        #     left[i] = max(left[i-1], A[i])
        # for i in range(n-2, -1, -1):
        #     right[i] = min(right[i+1], A[i])
        # print(left, right)
        # for i in range(n-1):
        #     if left[i] <= right[i+1]:
        #         return i+1


class Solution:
    def partitionDisjoint(self, A: List[int]) -> int:
        i = 1
        l_max = A[i-1]
        r_min = min(A[i:])

        while l_max > r_min:
            i += 1
            l_max = max(l_max, A[i-1])
            if A[i-1] == r_min:
                r_min = min(A[i:])
            
        return i

class Solution:
    def partitionDisjoint(self, A: List[int]) -> int:
        n = len(A)
        ma = [0] * n
        mi = [0] * n
        
        mi[-1] = A[-1]
        for i in range(n-2, -1, -1):
            mi[i] = min(A[i+1], mi[i+1])
        
        ma[0] = A[0]
        for i in range(1, n):
            ma[i] = max(A[i], ma[i-1])
        
        # print(mi)
        # print(ma)
        
        for i in range(n-1):
            if mi[i] >= ma[i]:
                return i + 1
        return n

class Solution:
    def partitionDisjoint(self, A: List[int]) -> int:
        max_left = [None] * len(A)
        min_right = [None] * len(A)
        
        m = A[0]
        for i in range(len(A)):
            m = max(m, A[i])
            max_left[i] = m

        m = A[-1]
        for i in range(len(A)-1, -1, -1):
            m = min(m, A[i])
            min_right[i] = m

        for i in range(1, len(A)):
            if max_left[i-1] <= min_right[i]:
                return i

class Solution:
    def partitionDisjoint(self, A: List[int]) -> int:
        max_left = list()
        min_right = list()
        
        for i in range(len(A)):
            left = A[i]
            if i == 0:
                max_left.append(left)
            elif max_left[i-1] > left:
                max_left.append(max_left[i-1])
            else:
                max_left.append(left)
                
            right = A[len(A) - 1 - i]
            if i == 0:
                min_right.append(right)
            elif min_right[i-1] < right:
                min_right.append(min_right[i-1])
            else:
                min_right.append(right)

        for i in range(len(A)):
            if max_left[i] <= min_right[len(A) - i - 2]:
                return i+1
        return 0

class Solution:
    def partitionDisjoint(self, A: List[int]) -> int:
        p = [None]*len(A)
        q = [None]*len(A)
        
        for i,v in enumerate(A):
            if i == 0:
                p[0] = v
            else:
                p[i] = max(p[i-1],v)
        
        for i,v in enumerate(reversed(A)):
            if i == 0:
                q[len(A)-1] = v
            else:
                q[len(A)-1-i] = min(q[len(A)-i],v)
        
        # print(p,q)
        for i in range(len(A)-1):
            if p[i] <= q[i+1]:
                return i+1
        
        return len(A)

from sortedcontainers import SortedList

class Solution:
    def partitionDisjoint(self, A: List[int]) -> int:
        left, right = SortedList(), SortedList(A)
        for i in range(len(A)-1):
            left.add(A[i])
            right.discard(A[i])
            if left[-1] <= right[0]:
                break
        return i + 1


class Solution:
    def partitionDisjoint(self, A: List[int]) -> int:
        i = 1
        l_max = A[i-1]

        d = Counter(A[i:])
        a_dict = OrderedDict(sorted(d.items()))
        r_min = next(iter(a_dict.items()))[0]

        while l_max > r_min:
            i += 1
            l_max = max(l_max, A[i-1])
            if a_dict[A[i-1]] > 1:
                a_dict[A[i-1]] -= 1
            else:
                del a_dict[A[i-1]]
                r_min = next(iter(a_dict.items()))[0]
                
        return i

# n^2 time to look at all subarrays
# n time to iterate backwards ?
class Solution:
    def partitionDisjoint(self, A: List[int]) -> int:
        min_right = min(A)
        max_left = 0
        
        min_from_right = []
        current_min_right = A[-1]
        for i in range(len(A) - 1, -1, -1):
            current_min_right = min(A[i], current_min_right)
            min_from_right.insert(0, current_min_right)
        
        for i in range(len(A)):
            current = A[i]
            max_left = max(max_left, current)
            min_right = min_from_right[i + 1] if i < len(A) else 0
            if max_left <= min_right:
                return i + 1

#         def check_partitions(a, b):
#             max_a = 0
#             for num in a:
#                 max_a = max(max_a, num)
#             min_b = maxsize
#             for num in b:
#                 min_b = min(min_b, num)
#             if max_a <= min_b and len(a) > 0 and len(b) > 0:
#                 return len(a)
#             return -1
        
#         min_left = maxsize
#         for i in range(1, len(A) + 1):
#             cand = check_partitions(A[0:i], A[i: len(A)])
#             if cand != -1:
#                 min_left = min(min_left, cand)
        
#         return min_left


class Solution:
    def partitionDisjoint(self, A: List[int]) -> int:
        
        maxlefts = []
        minrights = []
        
        m = A[0]
        for n in A:
            m = max(m, n)
            maxlefts.append(m)
        
        m = A[len(A) - 1]
        for n in A[::-1]:
            m = min(m, n)
            minrights.insert(0, m)
        
        for i in range(1, len(A)):
            if maxlefts[i - 1] <= minrights[i]: return i

class Solution:
    def partitionDisjoint(self, A: List[int]) -> int:
        res = 0
        v = A[0]
        max_sofar = v
        for i in range(len(A)):
            max_sofar = max(max_sofar, A[i])
            if A[i] < v:
                v = max_sofar
                res = i
                
        return res+1

class Solution:
    def partitionDisjoint(self, A: List[int]) -> int:
        # biggest = A[0]
        # newbiggest = A[0]
        # lenL = 1
        # total = 1
        # for itr in A[1:]:
        #     total += 1
        #     if itr < biggest:
        #         lenL = total
        #         biggest = newbiggest
        #     else:
        #         if itr > newbiggest:
        #             newbiggest = itr
        # return lenL
        disjoint = 0
        v = A[disjoint]
        max_so_far = v
        for i in range(len(A)):
            max_so_far = max(max_so_far, A[i])
            if A[i] < v: 
                disjoint = i
                v = max_so_far
        return disjoint + 1

class Solution:
    def partitionDisjoint(self, A: List[int]) -> int:
        n = len(A)
        mins = [float('inf')]*(n-1)+[A[-1]]
        for i in range(n-2, -1, -1):
            mins[i] = min(A[i], mins[i+1])

        maxi = 0
        for i in range(n-1):
            maxi = max(maxi, A[i])
            if maxi<=mins[i+1]:
                return i+1
        return -1

class Solution:
    def partitionDisjoint(self, A: List[int]) -> int:
        left_maxes = A[:]
        right_mins = A[:]
        
        for i in range(1, len(left_maxes)):
            if left_maxes[i] < left_maxes[i - 1]:
                left_maxes[i] = left_maxes[i - 1]
        
        for i in range(len(right_mins) - 2, -1, -1):
            if right_mins[i] > right_mins[i + 1]:
                right_mins[i] = right_mins[i + 1]
        
        for i in range(1, len(A)):
            if left_maxes[i - 1] <= right_mins[i]:
                return i