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.
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:
        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
    
    
