There is a room with n bulbs, numbered from 1 to n, arranged in a row from left to right. Initially, all the bulbs are turned off.
At moment k (for k from 0 to n - 1), we turn on the light[k] bulb. A bulb change color to blue only if it is on and all the previous bulbs (to the left) are turned on too.
Return the number of moments in which all turned on bulbs are blue.
 
Example 1:

Input: light = [2,1,3,5,4]
Output: 3
Explanation: All bulbs turned on, are blue at the moment 1, 2 and 4.

Example 2:
Input: light = [3,2,4,1,5]
Output: 2
Explanation: All bulbs turned on, are blue at the moment 3, and 4 (index-0).

Example 3:
Input: light = [4,1,2,3]
Output: 1
Explanation: All bulbs turned on, are blue at the moment 3 (index-0).
Bulb 4th changes to blue at the moment 3.

Example 4:
Input: light = [2,1,4,3,6,5]
Output: 3

Example 5:
Input: light = [1,2,3,4,5,6]
Output: 6

 
Constraints:

n == light.length
1 <= n <= 5 * 10^4
light is a permutation of  [1, 2, ..., n]

Difficulty: interview

Starter code:

class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        

Solutions:
class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        right = 0
        ans = 0
        for i in range(len(light)):
            if (light[i] > right):
                right = light[i]
            
            if (i + 1 == right):
                ans += 1
                
        return ans

'''
Time Limited
https://leetcode.com/submissions/detail/406886943/testcase/
'''

class Solution:
    def numTimesAllBlue(self, light):
        cnt, N = 0, len(light)
        bulbs = [0] * N
        for i, pos in enumerate(light, start = 1):
            pos -= 1
            if sum(bulbs[:pos]) == 2 * pos:
                bulbs[pos] = 2
                while pos + 1 < N and bulbs[pos+1] == 1:
                    bulbs[pos+1] = 2
                    pos += 1
                if sum(bulbs) == 2 * i:
                    cnt += 1
            else:
                bulbs[pos] = 1
        return cnt
        
class Solution:
    def numTimesAllBlue(self, light):
        cnt, seen = 0, set()
        for v in light:
            seen.add(v)
            if max(seen) == len(seen):
                cnt += 1 
        return cnt
    
class Solution:
    def numTimesAllBlue(self, light):
        cnt = 0
        maxV, size = 0, 0
        for v in light:
            size += 1
            if v > maxV: maxV = v
            if maxV == size:
                cnt += 1 
        return cnt

class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        def natural_sum(n):
            return (n*(n+1))//2
        count, s = 0, 0
        for i in range(len(light)):
            s += light[i]
            if natural_sum(i+1) == s:
                count += 1
        return count

class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        n = len(light)
        dp = [0] * (n+1)
        dp[0] = 2
        max_so_far = moment = 0
        
        for num in light:
            max_so_far = max(num, max_so_far)
            if dp[num-1] == 2:
                dp[num] = 2
                
                for b in range(num+1, max_so_far+1):
                    if dp[b] == 1:
                        dp[b] = 2
                    else:
                        break
                if dp[max_so_far] == 2: moment += 1
            else:
                dp[num] = 1
                
        return moment

class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        res = hi = on = 0
        for l in light:
            on += 1
            if l>hi:
                hi = l
            if on==hi:
                res+=1
        return res

import bisect
class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        sl = []
        count = 0
        for k in range(len(light)):
            bisect.insort_right(sl,light[k])
            if len(sl)==sl[-1]:
                count = count +1    
        return count


class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        ans = 0
        m = 0
        for i, j in enumerate(light):
            m = max(m, j)
            if i + 1 == m:
                ans += 1
        return ans


class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        ans = 0
        maxidx = 0
        
        for i, l in enumerate(light):
            maxidx = max(maxidx, l)
            if i+1 == maxidx:
                ans += 1
        return ans

class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        history = []
        count = 0
        limit = -1
        for i in light:
            history.append(light)
            limit = max(limit, i)
            if len(history) == limit:
                count += 1
        
        
        return count

class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        count=0
        right=0
        for i in range(len(light)):
            right = max(light[i], right)
            if right==i+1:
                count+=1
        
        return count

class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        h = []
        heapq.heapify(h)
        ret = 0
        for idx, l in enumerate(light):
            heapq.heappush(h, -l)
            max_val = -heapq.heappop(h)
            ret += max_val == idx + 1
            heapq.heappush(h, -max_val)
        return ret

class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        left_most_off = 0
        right_most_on = -1
        state = [0] * len(light)
        res = 0
        for e in light:
            e -= 1
            state[e] = 1
            right_most_on = max(right_most_on, e)
            if e == left_most_off:
                while left_most_off < len(light) and state[left_most_off]:
                    left_most_off += 1
                if left_most_off == len(light) or left_most_off > right_most_on:
                    res += 1
        
        return res


class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        cur_max=0
        count=0
        res=0
        for i in light:
            cur_max=max(cur_max,i)
            count+=1
            if count==cur_max:
                res+=1
        return res

class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        state = [] # on/off
        count = 0
        blue = 0
        last = 0
        
        for i in range(0, len(light)):
            state.append(False)
            
        for i, k in enumerate(light):
            state[k-1] = True
            
            # count how many are blue
            for c in range(last, len(light)):
                if not state[c]:
                    last = c
                    break
                blue += 1
                
            if blue == i+1:
                count += 1
                
        return count

class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        return sum(i == m for i, m in enumerate(itertools.accumulate(light, max), 1))

class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        on = [False]*len(light)
        n = len(light)
        blue,ans = 0,0
        for i in range(0,n):
            on[light[i]-1] = True
            while(blue<n and on[blue] == True):
                blue += 1
            if(blue == i+1):
                ans += 1
        return ans

from sortedcontainers import SortedList
class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        turned = SortedList()
        ret = 0
        
        for turn in light:
            turned.add(turn)
            if len(turned) == turned[-1]:
                ret += 1
        
        return ret

class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        n = len(light)
        mn, ma = n + 1, 0
        ans = 0
        for k, v in enumerate(light):
            ma, mn = max(ma, v), min(mn, v)
            if mn == 1 and ma - mn == k:
                ans += 1

        return ans


    def numTimesAllBlue(self, light: List[int]) -> int:
        result, right = 0, 0
        for i, num in enumerate(light, 1):
            right = max(right, num)
            result += (right == i)
        return result





class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        count = 0
        right = 0
        target = 0
        for n in reversed(light):
            right += 1
            target = max(target, len(light) - n + 1)
            if right == target:
                count += 1
            
        return count

class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        arr = [0]*(len(light)+1)
        most_right = 0
        count = 0
        for i, num in enumerate(light):
            if num > most_right:
                arr[num] = arr[most_right]+1 
                most_right = num 
            else:
                arr[most_right] += 1
                
            if arr[most_right] == most_right:
                count += 1 
                
        return count 

class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        
        
        cnt = 0
        checker =  0
        light_status = 0
        
        for i in range(0, len(light)):
            light_status |= 1 <<(light[i] - 1)
            
            checker |= 1 << i
            
            if checker == light_status:
                cnt+=1
        return cnt
            
        


class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        blue = right = 0
        
        for i, a in enumerate(light, 1):
            right = max(right, a)
            if i == right:
                blue += 1
                
        return blue

class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        r=0
        c=0
        for i in range(len(light)):
            r=max(r,light[i])
            if(r==i+1):
                c=c+1
        return c

class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        
        req = 1
        seen = set()
        ans = 0
        for i,n in enumerate(light, start=1):
            seen.add(n)
            
            if n == req:
                while req in seen:
                    seen.remove(req)
                    req += 1
            if not seen:
                ans += 1

        return ans

class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        num = 0 
        maxPos = 0 
        res = []
        for i in range(len(light)):
            maxPos = max(maxPos, light[i])
            num += 1
            if num == maxPos:
                res.append(i)
        return len(res)
                
                


class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        bSum=0
        pSum=0
        rr=0
        for i in range(len(light)):
            bSum+=light[i]
            pSum+=i+1
            if bSum==pSum: rr+=1
        return rr


class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        max_so_far = 0
        ret = 0
        for i, l in enumerate(light):
            max_so_far = max(max_so_far, l)
            ret += max_so_far == i + 1
        
        return ret

class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        first = 0
        last = 1
        on = [False] * len(light)
        ans = 0
        for l in light:
            # print(on, first, l, last)
            on[l-1] = True
            last = max(l, last)
            if first + 1 == l:
                while first<len(light) and on[first]:
                    first += 1
                if first == last:
                    ans += 1
        return ans

class Solution:
    def numTimesAllBlue(self, light):
        cnt = 0
        maxV, size = 0, 0
        for v in light:
            size += 1
            if v > maxV: maxV = v
            if maxV == size:
                cnt += 1
        return cnt

class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        right = result = 0
        for i, a in enumerate(light, 1):
            right = max(right, a)
            result += right == i
        return result
        
        
        


class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        c=0
        mx=0
        for i in range(len(light)):
            a = light[i]
            mx=max(mx,a)
            if mx==i+1:
                c+=1
        return c

# 
class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        # index for lights that should be on but is currently off
        pending_on = set()
        
        # index for lights that is turned on but not yet blue
        already_on = set()
        
        count = 0
        for idx, lgt in enumerate(light):
            lgt -= 1 # change from 1-base to 0-base
            if idx in already_on:
                already_on.remove(idx)
            else:
                pending_on.add(idx)
            
            if lgt in pending_on:
                pending_on.remove(lgt)
            else:
                already_on.add(lgt)
            
            if len(pending_on) == 0:
                count += 1
        
        return count


##we need to find out for indices i which ones such that a[0],a[1],...,a[i] are permutations of 1,2,...,i+1.
class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        minimum = len(light)+1
        maximum = 0
        moments = 0
        for index,num in enumerate(light):
            minimum = min(num,minimum)
            maximum = max(num,maximum)
            if minimum == 1 and maximum == index+1:
                moments += 1
        return moments


class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        yellow, blue = set(), set()
        moment = 0
        for bulb in light:
            if bulb == 1 or bulb - 1 in blue:
                blue.add(bulb)
                t = bulb+1
                while t in yellow:
                    yellow.remove(t)
                    blue.add(t)
                    t += 1
            else:
                yellow.add(bulb)
            if not yellow:
                moment += 1
        return moment


class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        n = len(light)
        ans = 0
        bulbs = [0 for _ in range(n)]
        zero_i, one_i = 0, 0
        for i in light:
            bulbs[i-1] = 1
            if zero_i == i-1:
                j = i-1
                while j < n and bulbs[j] == 1:
                    j += 1
                zero_i = j
            one_i = max(one_i, i-1)
            if one_i < zero_i:
                ans += 1
                
        return ans

class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        min_seen, max_seen = float('inf'), float('-inf')
        times = 0
        for i, moment in enumerate(light):
            min_seen = min(min_seen, moment)
            max_seen = max(max_seen, moment)
            times += (max_seen - min_seen == i) and min_seen == 1 and max_seen == i + 1
        return times


class Solution:
    def numTimesAllBlueQuad(self, light: List[int]) -> int:
        blue = 0
        lights = [0 for l in light]
        
        for l in light:
            lights[l-1] = 1
            
            if all([x == 1 for x in lights[:l-1]]):
                blue += 1
                print(l)
        
        return blue
            
    def numTimesAllBlue(self, light: List[int]) -> int:
        count = 0
        sums = [0] * (len(light) + 1)
        for idx, l in enumerate(light):
            sums[idx+1] = sums[idx] + l
            
        print(sums)
        for idx, l in enumerate(light):
            if sums[idx+1] == self.required(idx+1):
                count += 1
        
        return count
        
    @staticmethod
    def required(n):
        return ((n+1)*n)//2

class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        n = len(light)
        rMin = [light[-1]]*n
        for i in range(n-2,-1,-1):
            rMin[i] = min(rMin[i+1],light[i])
        
        out = 1
        lmax = 0
        for i in range(n-1):
            lmax = max(lmax,light[i])
            if lmax <= rMin[i+1]:
                out+=1
        return out
        


class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        if len(light) == 0:
            return 0
        dic = {}
        count = 0
        flag = True
        Max = light[0]
        for i, item in enumerate(light):
            dic[item] = True
            Max = max(light[i], Max)
            if Max == len(dic):
                count += 1
                continue
            elif Max > len(dic):
                flag = False
            else:
                for j in range(item, 0, -1):
                    if j not in dic:
                        flag = False
            if flag:
                count += 1
            flag = True
        return count


class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        res = hi = on = 0
        for l in light:
            on += 1
            if l>hi:
                hi = l
            if on==hi:
                res+=1
        return res
            
            
            


class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        b=0
        ans=0
        k=0
        l=[0 for i in range(len(light))]
        for i in range(len(light)):
            a=light[i]-1
            if b==a:
                l[a]=2
                c=a+1
                #print(l,a,c)
                b=c
                while c<len(light) and l[c]==1:
                    l[c]=2
                    b=c+1
                    k-=1
                    c+=1
            else:
                if a>0 and l[a-1]==2:
                    l[a]=2
                    b=l[a]+1
                else:
                    l[a]=1
                    k+=1
            #print(i,l,k,a,b)
            if k==0:
                ans+=1
        return ans


class Solution:
    # 2:00
    '''
    - light yellow
    - if left is blue
        - keep on marking everything to the right blue
    - if in the end number of yello = 0, increment ans
    - key thing to notice is that the blue only start propogating when number 1 bulb is lighted
    
    '''
    
    def numTimesAllBlue(self, light: List[int]) -> int:
        nyellow = 0
        nblue = 0
        dx = {}
        YELLOW = 0
        BLUE = 1
        OFF = 2
        for b in light:
            dx[b] = OFF
        ans = 0
        for i in range(len(light)):
            
            curr = light[i]
            dx[curr] = YELLOW
            nyellow  += 1
            check = False
            
            if curr == 1 or dx[curr - 1] == BLUE:
                check  = True
            if check:
                for j in range(curr, len(light)+1):
                    if dx[j] == OFF:
                        break
                    else:
                        nyellow  -= 1
                        nblue += 1
                        dx[j] = BLUE
                    
            # print(light[i], nyellow)
            if nyellow == 0:
                ans += 1
        return ans
                


class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        n = max(light)
        bulb_status = ['off'] * (n + 1)
        
        count = 0
        num_on = 0
        num_blue = 0
        
        for i in light:
            
            bulb_status[i] = 'on'
            num_on += 1
            
            while i <= n and (i == 1 or bulb_status[i - 1] == 'blue'):
                if bulb_status[i] == 'off':
                    break
                    
                bulb_status[i] = 'blue'
                num_blue += 1
                num_on -= 1
                
                i += 1
                
            if num_on == 0 and num_blue > 0:
                count += 1
        
        return count

class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        
        maxBulb = 0
        maxBlue = 0
        count = 0
        
        moments = [False for i in range(len(light))]     
        for idx, bulb in enumerate(light):
            maxBulb = max(maxBulb, bulb)
            moments[bulb-1] = True
            if bulb == 1 or maxBlue == bulb-1:
                maxBlue = bulb
                i = bulb+1
                while(i <= len(light) and moments[i-1]):
                    maxBlue = i
                    i+=1
    
            if maxBlue == maxBulb:
                count+=1
        return count


class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        
        # use a min and max counter when min == max => all bulbs are blue
        
        min_counter = -1
        max_counter = -1
        
        turned_on = [0] * len(light)
        
        moments = 0
        for bulb in light:
            bulb = bulb-1
            max_counter = max(max_counter, bulb)
            turned_on[bulb] = 1
            
            while min_counter+1 < len(turned_on) and turned_on[min_counter+1] == 1: 
                min_counter += 1
                
            if max_counter == min_counter:
                moments += 1
        
        return moments


class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        if len(light) == 1:
            return 1
        mx, mi, s = float('-inf'), float('inf'), 0
        
        res = 0 
        for i, num in enumerate(light):
            s += num
            mx = max(mx, num)
            mi = min(mi, num)
            if mi == 1 and mx == i+1 and s == (i+1)*(i+2)//2:
                res += 1
        
        return res


class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        light = [i-1 for i in light]
        bulbs = [0 for _ in range(len(light))]
        on,blue = set(),set()
        res = 0
        #print(bulbs)
        #print(light)
        n = len(light)
        total = 0
        for moment in light:
            #print(bulbs,moment)
            if moment == 0:
                bulbs[0] = 2
                blue.add(0)
            elif bulbs[moment-1] == 2:
                bulbs[moment] = 2
                blue.add(moment)
            else:
                bulbs[moment] = 1
                on.add(moment)
            if bulbs[moment] == 2:
                #print('turning things blue',bulbs[moment+1] if moment+1 < n else -1)
                i = moment+1
                while i < n and bulbs[i] == 1:
                    bulbs[i] = 2
                    blue.add(on.remove(i))
                    i += 1
            res += 1 if blue and not on else 0
        return res

class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        # Moments at which max light is last consec on
        max_light_on = -1
        last_consecutive_on = -1
        
        all_blue = 0
        
        for light_bulb in light:
            # Turn this light on by negating it
            light_index = abs(light_bulb) - 1
            light[light_index] = -light[light_index]
            
            # Check if this is the max light on
            max_light_on = max(max_light_on, light_index)
            
            # Check if this is the last consecutive light on starting from 0
            while last_consecutive_on < len(light) - 1 and light[last_consecutive_on + 1] < 0:
                last_consecutive_on += 1
            
            if max_light_on == last_consecutive_on:
                all_blue += 1
        
        return all_blue

class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        sum  = total = count = 0
        
        for i in range(len(light)):
            sum += i+1
            total += light[i]
            if sum == total:
                count+=1
        return count


class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        min_off = 1
        max_on = float('-inf')
        count = 0
        
        blue = [0]*(len(light)+1)
        
        for i in range(len(light)):
            blue[light[i]] = 1
            max_on = max(max_on,light[i])
            if light[i] == min_off:
                while min_off <= len(light) and blue[min_off] == 1:
                    min_off +=1
            if max_on < min_off:
                count += 1
                
        return count 

class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        light = [i-1 for i in light]
        bulbs = [0 for _ in range(len(light))]
        on,blue = set(),set()
        res = 0
        print(bulbs)
        print(light)
        n = len(light)
        total = 0
        for moment in light:
            #print(bulbs,moment)
            if moment == 0:
                bulbs[0] = 2
                blue.add(0)
            elif bulbs[moment-1] == 2:
                bulbs[moment] = 2
                blue.add(moment)
            else:
                bulbs[moment] = 1
                on.add(moment)
            if bulbs[moment] == 2:
                #print('turning things blue',bulbs[moment+1] if moment+1 < n else -1)
                i = moment+1
                while i < n and bulbs[i] == 1:
                    bulbs[i] = 2
                    blue.add(on.remove(i))
                    i += 1
            res += 1 if blue and not on else 0
        return res

class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        light = sorted([(light[i], i) for i in range(len(light))], key=lambda t: t[0])
        go_over = list([t[1] for t in light])
                     
        smallest_distance_left_until_blue = 0
        count = 0
        for i in range(len(go_over)):
            smallest_distance_left_until_blue = max(smallest_distance_left_until_blue - 1, 0, go_over[i] - i)
            if smallest_distance_left_until_blue == 0:
                count += 1
            
        return count


import collections

class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        n = len(light)
        ans = count_blue = 0
        state = collections.defaultdict(int)
        
        for j, bulb in enumerate(light):
            #if prev bulb is blue
            if bulb == 1 or state[bulb-1]==2:
                state[bulb] = 2
                count_blue+=1
            else:
                # else just set to lit
                state[bulb] = 1
            
            
            # if curre bulb is blue, set next bulb to blue if they are lit
            if state[bulb] == 2:
                i = bulb+1
                while i<n+1 and state[i]==1:
                    count_blue+=1
                    state[i] = 2
                    i+=1
            if count_blue== j+1:
                ans += 1
            
        return ans
                


def fillMissingSet(highest_bulb, bulbs_missing, bulbs_lit, difference):
    for i in range(highest_bulb-difference,highest_bulb):
        if i not in bulbs_lit:
            bulbs_missing.add(i)

class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        highest_bulb = 1
        difference = 0
        bulbs_lit = set()
        bulbs_missing = set()
        instances=0
        fillMissingSet(light[0], bulbs_missing, bulbs_lit, difference)
        for i in range(len(light)):
            difference = 0
            if highest_bulb < light[i]:
                difference = light[i]-highest_bulb
                highest_bulb = light[i]
            bulbs_lit.add(light[i])
            if light[i] in bulbs_missing:
                bulbs_missing.remove(light[i])
            fillMissingSet(highest_bulb, bulbs_missing, bulbs_lit, difference)
            if len(bulbs_missing) == 0:
                instances +=1
            #print(highest_bulb, bulbs_missing, bulbs_lit, instances, difference)
        return instances
    



import heapq
class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        q = []
        res = 0
        for num in light:
            heapq.heappush(q, -num)
            if -q[0] == len(q):
                res += 1
        return res


class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        '''m = set()
        flag, c = -1, 0
        for i in range(len(light)):
            m.add(light[i])
            for j in range(i+1,0,-1):
                if j not in m:
                    flag = 1
                    break
            if flag == 1:
                flag = -1
            else:
                c += 1
        return c'''
        res = 0
        curr = -1
        for p,q in enumerate(light):
            curr = max(curr,q)
            if curr == p+1:
                res += 1
        return res
            


class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        n = len(light)
        states = [0] * n
        yellow_lights = set()
        all_blue_counter = 0
        
        for i in range(n): 
            bulb = light[i] - 1
            
            if bulb == 0 or states[bulb-1] == 2:
                states[bulb] = 2
            elif states[bulb-1] != 2:
                states[bulb] = 1
                yellow_lights.add(bulb)
            
            if states[bulb] == 2:
                for j in range(bulb + 1, n):
                    if states[j] == 1:
                        yellow_lights.remove(j)
                        states[j] = 2
                    else: break
            
            if len(yellow_lights) == 0:
                all_blue_counter += 1

        return all_blue_counter

class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        moment_count = 0
        lit_idx = -1
        
        idx_map = {}
        
        for idx, moment in enumerate(light):
            idx_map[moment] = idx
            
        for moment in range(1, len(light) + 1):
            idx = idx_map[moment]
            light[idx] = 'L'
            
            if idx == lit_idx + 1:
                for l_idx in range(lit_idx + 1, len(light)):
                    if light[l_idx] == 'L':
                        lit_idx += 1
                    else:
                        break
                        
            if lit_idx + 1 == moment:
                moment_count += 1
        
        return moment_count

class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        max_light = 0
        num=0
        res = 0
        for i,l in enumerate(light):
            max_light = max(max_light,l)
            
            print(max_light)
            if i+1>=max_light:
                res+=1
        return res

class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
      res = 0
      grid = [0]*len(light)
      dicts = {}
      for turn in light:
        if turn == 1:
          grid[turn-1] = 1
          start = turn - 1
          while start < len(light):
            if grid[start] != 0:
              if start in dicts: del dicts[start]
              grid[start] = 1
              start += 1
            else:
              break
          if not dicts: res += 1
        else:
          if grid[turn - 2] == 1:
            grid[turn - 1] = 1
            start = turn - 1
            breaked = False
            while start < len(light):
              if grid[start] != 0:
                if start in dicts: del dicts[start]
                grid[start] = 1
                start += 1
              else:
                break
            if not dicts: res += 1           
          else:
            grid[turn -1] = 2
            dicts[turn - 1] = 1
      return res
            
            
        


class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        len_lis = len(light)
        lis = [[] for x in range(len_lis+2)]
        tot = 0
        for i in range(len_lis):
            if(light[i] > 1 and lis[light[i]-1] and light[i] < len_lis and lis[light[i]+1]):
                end = lis[light[i]+1][1]
                start = lis[light[i]-1][0]
            elif(light[i] > 1 and lis[light[i]-1]):
                start = lis[light[i]-1][0]
                end = light[i]
            elif(light[i] < len_lis and lis[light[i]+1]):
                start = light[i]
                end = lis[light[i]+1][1]
            else:
                start = light[i]
                end = light[i]
            if(end-start == i and start == 1):
                tot += 1
            lis[end] = [start, end]
            lis[start] = [start, end]
            #print(lis)
        return tot

class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        ranges = {}
        r = 0
        for l in light:
            if l + 1 not in ranges and l - 1 not in ranges:
                ranges[l] = (l, l)
            elif l + 1 in ranges and l - 1 not in ranges:
                _, rr = ranges[l + 1]
                ranges[l] = ranges[rr] = (l, rr)
                if rr != l + 1:
                    del ranges[l + 1]
            elif l - 1 in ranges and l + 1 not in ranges:
                ll, _ = ranges[l - 1]
                ranges[ll] = ranges[l] = (ll, l)
                if ll != l - 1:
                    del ranges[l - 1]
            else:
                ll, _ = ranges[l - 1]
                _, rr = ranges[l + 1]
                ranges[ll] = ranges[rr] = (ll, rr)
                if ll != l - 1:
                    del ranges[l - 1]
                if rr != l + 1:
                    del ranges[l + 1]
            # print(ranges)
            if len(ranges) == 1:
                r += (list(ranges.items())[0][0] == 1)
            elif len(ranges) == 2:
                r += (len(set(ranges.values())) == 1 and list(ranges.values())[0][0] == 1)
        return r

class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        right = res = 0
        for i, v in enumerate(light):
            right = max(right, v)
            res += right == i + 1
        return res



class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        max_v = 0
        res = 0
        
        for i,v in enumerate(light):
            max_v = max(max_v, v)
            if max_v == i+1:
                res += 1
        
        return res

class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        n = 0
        highest = 0
        ans = 0
        
        for bulb in light:
            n += 1
            highest = max(highest, bulb)
            if highest == n:
                ans += 1
        
        return ans

class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        '''arr=[0]*(len(light)+1)
        cnt=0
        max_1=light[0]
        i=0
        while i<len(light):
            arr[light[i]]=1           
            if max_1<light[i]:
                max_1=light[i] 
            if sum(arr)==max_1:
                cnt+=1
            i+=1
        return(cnt)'''
        
        cnt=0
        max_1=light[0]
        for i in range(0,len(light)):
            max_1=max(max_1,light[i])
            #print(max_1,i+1)
            if max_1==i+1:
                cnt+=1
        return(cnt)

def parent(p,i):
    if p[i]!=i:
        p[i]=parent(p,p[i])
    return p[i]


class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        p=[0]*len(light)
        c=[0]*len(p)
        for i in range(len(p)):
            p[i]=i
        x=0
        ans=0
        for j in light:
            i=j-1
            x+=1
            c[i]=1
            if i-1>-1 and c[i-1]!=0:
                p[i]=parent(p,i-1)
                c[p[i]]+=1
            if i+1<len(light) and c[i+1]!=0:
                c[p[i]]+=c[i+1]
                p[i+1]=p[i]
            if c[p[i]]==x and c[0]!=0:
                #print(c)
                #print(p)
                #print()
                ans+=1
        return ans

class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        rolling_min = light[0]
        rolling_max = light[0]
        r = 0
        for i, l in enumerate(light):
            rolling_min = min(rolling_min, l)
            rolling_max = max(rolling_max, l)
            r += (rolling_min == 1 and rolling_max == i + 1)
        return r

from heapq import heappush,heappop,heapify
class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        n=len(light)
        a=[]
        ans=0
        for i in range(n):
            heappush(a,-1*(light[i]))
            if len(a)==i+1:
                temp=-1*heappop(a)
                if  temp==i+1:
                    ans+=1
                heappush(a,-1*temp)
        return ans

class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        maximum = 1
        res = 0
        for i, val in enumerate(light):
            maximum = max(maximum, val)
            if i+1 == maximum:
                res += 1
        return res

class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        res, mx = 0, 0
        for i, v in enumerate(light, 1):
            mx = max(v, mx)
            res += (i == mx)
        return res

class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        right = res = 0
        for i, a in enumerate(light, 1):
            right = max(right, a)
            res += right == i
        return res


class Solution:
    # 2:00
    '''
    - light yellow
    - if left is blue
        - keep on marking everything to the right blue
    - if in the end number of yello = 0, increment ans
    - key thing to notice is that the blue only start propogating when number 1 bulb is lighted
    
    '''
    
    def numTimesAllBlue(self, light: List[int]) -> int:
        nyellow = 0
        nblue = 0
        dx = {}
        YELLOW = 0
        BLUE = 1
        OFF = 2
        for b in light:
            dx[b] = OFF
        ans = 0
        for i in range(len(light)):
            
            curr = light[i]
            dx[curr] = YELLOW
            nyellow  += 1
            check = False
            
            if curr == 1 or dx[curr - 1] == BLUE:
                check  = True
            if check:
                for j in range(curr, len(light)+1):
                    if dx[j] == OFF:
                        break
                    else:
                        nyellow  -= 1
                        nblue += 1
                        dx[j] = BLUE
                    
            print((light[i], nyellow))
            if nyellow == 0:
                ans += 1
        return ans
                


class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        total = 0
        count = 0
        for k in range(len(light)):
            total += light[k]
            if total == ((k + 1) * (k + 2)) // 2:
                count += 1
        return count


class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        res = 0
        n = len(light)
        counter = collections.Counter()
        for i in range(n):
            counter[light[i]] += 1
            if counter[light[i]] == 0:
                counter.pop(light[i])
            counter[i+1] -= 1
            if counter[i+1] == 0:
                counter.pop(i+1)
            if not counter:
                res += 1
        return res

class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        maxv = 0
        result =0
        
        for i, num in enumerate(light):
            maxv = max(maxv, num)
            if maxv== i+1: result+=1
        return result
            


class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        status = [0]*(len(light)+1)
                    
        k = 0
        number_of_blues = 0
        count = 0
        
        while(k < len(light)):
            idx = light[k]
            status[idx] = 1
            
            if idx == 1:
                status[1] = 2
                number_of_blues += 1
                
            for i in range(idx,len(light)+1):
                if i == idx and status[i] == 2:
                    continue
                if status[i] == 1 and status[i-1] == 2:
                    status[i] = 2
                    number_of_blues += 1
                else:
                    break
                    
            if number_of_blues == k+1:
                count += 1


            #print(status)   
            k += 1

        return count
            
                
                
                


class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
      res = 0
      grid = [0]*len(light)
      dicts = {}
      for turn in light:
        if turn == 1:
          grid[turn-1] = 1
          start = turn
          while start < len(light):
            if grid[start] != 0:
              if start in dicts: del dicts[start]
              grid[start] = 1
              start += 1
            else:
              break
          if not dicts: res += 1
        else:
          if grid[turn - 2] == 1:
            grid[turn - 1] = 1
            start = turn
            breaked = False
            while start < len(light):
              if grid[start] != 0:
                if start in dicts: del dicts[start]
                grid[start] = 1
                start += 1
              else:
                break
            if not dicts: res += 1           
          else:
            grid[turn -1] = 2
            dicts[turn - 1] = 1
      return res
            
            
        


class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        res = 0
        n = len(light)
        
        # Actual turned on light (positive)
        # Required turned on light (negative)
        counter = collections.Counter()
        for i in range(n):
            counter[light[i]] += 1
            if counter[light[i]] == 0:
                counter.pop(light[i])
            
            counter[i+1] -= 1
            if counter[i+1] == 0:
                counter.pop(i+1)
            
            if not counter:
                res += 1
        return res

class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        s = 0
        max_index = 0
        count = 0
        for i in range(len(light)):
            s += 1
            if light[i] > max_index:
                max_index = light[i]
            
            #print(f\"s: {s} max_index: {max_index} i: {i}\")
            if i+1 == max_index:
                count += 1
                
        return count

class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        curr_max = 0
        res = 0
        for idx, val in enumerate(light):
            curr_max = max(curr_max, val)
            if curr_max == idx + 1:
                res += 1
        return res
            
            


class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        max_ind = 0
        res = 0
        for t in range(len(light)):
            max_ind = max(max_ind, light[t])
            if max_ind == t+1:
                res += 1
        return res

class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        max_on = 0
        count = 0
        for idx, bulb in enumerate(light):
            max_on = max(max_on, bulb)
            
            if max_on == idx+1:
                count += 1
        
        return count

class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        res = right = 0
        for i, n in enumerate(light):
            # update right most bulb's number
            right = max(right, n)
            # right most bulb's number equals to number of processed bulbs
            # meaning all bulbs to the left are ON
            res += 1 if right == i + 1 else 0
        return res


class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        right = -1
        res = 0
        for i in range(len(light)):
            right = max(light[i], right)
            if right == i+1:
                res += 1
        return res

class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        bulb_ranges = {}
        lights_on = 0
        result = 0
        for l in light:
            lights_on += 1
            left = right = None
            if l - 1 not in bulb_ranges and l + 1 not in bulb_ranges:
                left = l
                right = l
            else:
                if l - 1 in bulb_ranges:
                    cur_left, cur_right = bulb_ranges[l - 1]
                    left = cur_left
                    right = l
                    del bulb_ranges[l - 1]
                if l + 1 in bulb_ranges:
                    cur_left, cur_right = bulb_ranges[l + 1]
                    if left is None:
                        left = l
                    right = cur_right
                    del bulb_ranges[l + 1]
                    
            bulb_ranges[left] = (left, right)
            bulb_ranges[right] = (left, right)
            if left == 1 and right - left + 1 == lights_on:
                result += 1
        
        return result

class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        res = nums_on = last_pos = 0
        for pos in light:
            nums_on += 1
            if pos > last_pos:
                last_pos = pos
            if nums_on == last_pos:
                res += 1
                
        return res

class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        last_on = 0
        heap = []
        heapq.heapify(heap)
        result = 0
        for i, num in enumerate(light):
            if num == last_on + 1:
                last_on = num
                if not heap: result += 1
                while(heap):    
                    top = heapq.heappop(heap)
                    if top == last_on+1:
                        last_on += 1
                    else:
                        heapq.heappush(heap, top)
                        break
                    if not heap:
                        result+=1
            else:
                heapq.heappush(heap, num)
        return result

class Solution:
    def numTimesAllBlue(self, A):
        right = res = 0
        for i, a in enumerate(A, 1):
            right = max(right, a)
            res += right == i
        return res

class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        _min = len(light)+1
        _max = 0
        missing = set()
        num_moments = 0
        
        for i in light:
            if i > _max:
                if _max != 0:
                    for j in range(_max+1, i):
                        missing.add(j)
                _max = i
            if i < _min:
                if _min != len(light)+1:
                    for j in range(i+1, _min):
                        missing.add(j)
                _min = i
            if i in missing:
                missing.remove(i)
            if len(missing) == 0 and _min < 2:
                num_moments+=1
        return num_moments
                
        
#         number_of_moments = 0
#         max_seen_value = 0
#         min_seen_index = len(light)+1
        
#         for i in range(len(light)):
#             if abs(max_seen - light[i]) == 1 and min_seen_index == 0:
#                 number_of_moments += 1
            
#             if light[i] > max_seen:
#                 max_seen = light[i]-1
            
#             if min_seen_index < light[i] - 1:
#                 min_seen_index == light[i] - 1
            
            
#         return number_of_moments 
    
    
    # max = 3, index = 2
    # max = 3, index = 1
    # max = 4, index = 1
    # max = 4, index = 0
    
    
#     light_on = [0]*len(light)
#         number_of_moments = 0
#         farthest_pos = 0
#         for i in range(len(light)):
#             all_blue = True
#             light_on[light[i]-1] = 1
#             if light[i] - 1 > farthest_pos:
#                 farthest_pos = light[i] - 1
#             for j in range(farthest_pos):
#                 if light_on[j] == 0:
#                     all_blue = False
#                     break;
#             if all_blue:
#                 number_of_moments += 1
            
#         return number_of_moments  


class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        max_ = 0
        output = 0
        for i in range(len(light)):
            max_ = max(max_, light[i])
            if max_ == i+1:
                output += 1
        return output


class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        res = 0
        high = 0
        on = 0
        
        for l in light:
            on += 1
            if l > high:
                high = l
            if on == high:
                res += 1
        
        return res

class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        # count times when all the lights on the left are on
        # which is: when the max idx of the lights on == the the number of lights on. 
        max_idx = float('-inf')
        cnt = 0
        for i in range(len(light)):
            max_idx = max(max_idx, light[i])
            if max_idx == i + 1:
                cnt += 1
        return cnt
        
            


class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        _max = 0
        _min = 1
        num_moments = 0
        for i in range(len(light)):
            if _max < light[i]:
                _max = light[i]
            
            if _max - _min == i:
                num_moments += 1
        return num_moments
#         _min = len(light)+1
#         _max = 0
#         missing = set()
#         num_moments = 0
        
#         for i in light:
#             if i > _max:
#                 if _max != 0:
#                     for j in range(_max+1, i):
#                         missing.add(j)
#                 _max = i
#             if i < _min:
#                 if _min != len(light)+1:
#                     for j in range(i+1, _min):
#                         missing.add(j)
#                 _min = i
#             if i in missing:
#                 missing.remove(i)
#             if len(missing) == 0 and _min < 2:
#                 num_moments+=1
#         return num_moments
                
        
#         number_of_moments = 0
#         max_seen_value = 0
#         min_seen_index = len(light)+1
        
#         for i in range(len(light)):
#             if abs(max_seen - light[i]) == 1 and min_seen_index == 0:
#                 number_of_moments += 1
            
#             if light[i] > max_seen:
#                 max_seen = light[i]-1
            
#             if min_seen_index < light[i] - 1:
#                 min_seen_index == light[i] - 1
            
            
#         return number_of_moments 
    
    
    # max = 3, index = 2
    # max = 3, index = 1
    # max = 4, index = 1
    # max = 4, index = 0
    
    
#     light_on = [0]*len(light)
#         number_of_moments = 0
#         farthest_pos = 0
#         for i in range(len(light)):
#             all_blue = True
#             light_on[light[i]-1] = 1
#             if light[i] - 1 > farthest_pos:
#                 farthest_pos = light[i] - 1
#             for j in range(farthest_pos):
#                 if light_on[j] == 0:
#                     all_blue = False
#                     break;
#             if all_blue:
#                 number_of_moments += 1
            
#         return number_of_moments  


class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        
        
        moment = 0
        bulbsOn = 0
        
        for i in range(len(light)):
            bulbsOn = max(bulbsOn, light[i])
            
            if bulbsOn == i + 1:
                moment += 1
                
        return moment

class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        res = 0
        numBlue = 0
        status = [0] * len(light)
        
        for i in range(len(light)):
            
            idx = light[i] - 1
            if idx == 0 or status[idx - 1] == 2:
                status[idx] = 2
                numBlue += 1
                idx += 1
                while idx != len(light) and status[idx] == 1:
                    status[idx] = 2
                    numBlue += 1
                    idx += 1
                
            else:
                status[idx] = 1
            # print(status)
            # print(numBlue)
            # print(i + 1)
            if numBlue == i + 1:
                res += 1
        
        return res


class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        res = 0
        right = 0
        
        for idx in range(len(light)):
            right = max(right, light[idx])
            
            if right == idx + 1:
                res += 1
        
        return res


class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        count = 0
        max_idx = 0
        res = 0
        for p in light:
            max_idx = max(max_idx, p-1)
            count += 1
            if count == max_idx + 1:
                res += 1
        
        return res


class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:

        right = res = 0
        for i, a in enumerate(light, 1):
            right = max(right, a)
            res += right == i
        return res

class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        def cumulative_sum(input_list):
            curSum, cumSum = 0, []
            for i in input_list:
                curSum += i
                cumSum.append(curSum)
            return cumSum
        
        cumSum = cumulative_sum(light)
        cumSum_target = cumulative_sum(list(range(1, len(light)+1)))
        
        return sum([cumSum[i]==cumSum_target[i] for i in range(len(cumSum))])

class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        
        moments = 0 
        pair = [light[0], light[0] - 1]
        for i in range(1, len(light)):    
            if pair[1] == 0: 
                moments += 1
            
            if pair[0] > light[i]: 
                pair[1] -= 1
            else: 
                pair[1] = light[i] - pair[0] + pair[1] - 1
                pair[0] = light[i]
            
        if pair[1] == 0: 
            moments += 1
        
        return moments


class Solution:
    def numTimesAllBlue(self, light: List[int]) -> int:
        if not light: return int()
        
        answer = right = int()
        
        for i, light in enumerate(light):
            right   = max(right, light)
            if i + 1 == right:
                answer += 1
        
        return answer