class Solution:
    def minFlipsMonoIncr(self, S):
        """
        :type S: str
        :rtype: int
        """
        n=len(S)
        if n==0:
            return 0
        count=0
        nums=[0 for i in range(n)]
        for i in range(n):
            if S[i]=="1":
                nums[i]=1
        left,right=[0 for i in range(n)],[0 for i in range(n)]
        for i in range(1,n,1):
            if nums[i-1]==1:
                left[i]=left[i-1]+1
            else:
                left[i]=left[i-1]
        for i in range(n-2,-1,-1):
            if nums[i+1]==0:
                right[i]=right[i+1]+1
            else:
                right[i]=right[i+1]
        temp_left,temp_right=0,n-1
        left_minus,right_minus=0,0
        while temp_left<temp_right:
            while temp_left<n and nums[temp_left]==0:
                temp_left+=1
            while temp_right>=0 and nums[temp_right]==1:
                temp_right-=1
            if temp_left>=temp_right:
                break
            if left[temp_right]-left_minus>=right[temp_left]-right_minus:
                right_minus+=1
                temp_right-=1
                count+=1
            else:
                left_minus+=1
                temp_left+=1
                count+=1
        return count


s=Solution()
graph = [1,0,1,0,1]
print(s.threeEqualParts(graph))