There is a one-dimensional garden on the x-axis. The garden starts at the point 0 and ends at the point n. (i.e The length of the garden is n).
There are n + 1 taps located at points [0, 1, ..., n] in the garden.
Given an integer n and an integer array ranges of length n + 1 where ranges[i] (0-indexed) means the i-th tap can water the area [i - ranges[i], i + ranges[i]] if it was open.
Return the minimum number of taps that should be open to water the whole garden, If the garden cannot be watered return -1.
 
Example 1:

Input: n = 5, ranges = [3,4,1,1,0,0]
Output: 1
Explanation: The tap at point 0 can cover the interval [-3,3]
The tap at point 1 can cover the interval [-3,5]
The tap at point 2 can cover the interval [1,3]
The tap at point 3 can cover the interval [2,4]
The tap at point 4 can cover the interval [4,4]
The tap at point 5 can cover the interval [5,5]
Opening Only the second tap will water the whole garden [0,5]

Example 2:
Input: n = 3, ranges = [0,0,0,0]
Output: -1
Explanation: Even if you activate all the four taps you cannot water the whole garden.

Example 3:
Input: n = 7, ranges = [1,2,1,0,2,1,0,1]
Output: 3

Example 4:
Input: n = 8, ranges = [4,0,0,0,0,0,0,0,4]
Output: 2

Example 5:
Input: n = 8, ranges = [4,0,0,0,4,0,0,0,4]
Output: 1

 
Constraints:

1 <= n <= 10^4
ranges.length == n + 1
0 <= ranges[i] <= 100

Difficulty: interview

Starter code:

class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        

Solutions:
class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        for i,r in enumerate(ranges):
            l = max(0,i-r)
            ranges[l] = max(i+r, ranges[l])
            
        res = lo = hi = 0            
        while hi < n:
            lo, hi = hi, max(ranges[lo:hi+1])
            if hi == lo: return -1
            res += 1
        return res 

class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        if not ranges: return 0
        N = len(ranges)
        # For all location of taps, store the largest right reach point
        max_right_end = list(range(N))
        for i, a in enumerate(ranges):
            max_right_end[max(i - a, 0)] = min(i + a, N-1)
        print(max_right_end)
        res, l, r = 0, 0, max_right_end[0]
        while True:
            res += 1
            # if r can reach to the end of the whole garden, return res
            if r>=N-1:return res
            new_r = max(max_right_end[l:r+1])
            # if next r is same as current r, it means we can not move forward, return -1
            if new_r == r:return -1
            l, r = r, new_r


class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        
#         from collections import defaultdict
        
#         if n==0:
#             return -1
        
#         plots = defaultdict(list)
#         for i in range(n):
#             l, r = i - ranges[i], i + ranges[i]
#             for j in [k for k in range(n) if k>=l and k<=r]:
#                 plots[j].append(i)
        
#         print(plots)
#         if len(plots.keys()) == n:
#             for i in plots.items():
#                 print(i)
#         else:
#             return -1

        def parse_ranges(ranges):
            intervals = []
            
            for idx, distance in enumerate(ranges):
                left = max(0, idx-distance)
                right = min(n, idx+distance)
                intervals.append([left, right])
            
            return intervals
        
        watered = []
        intervals = parse_ranges(ranges)
        intervals.sort(key=lambda time: (time[0], -time[1]))
        for start, end in intervals:
            if watered and watered[-1][1] >= end: 
                continue
            if watered and start - watered[-1][1] > 0: 
                return -1
            
            if len(watered) >= 2 and start <= watered[-2][1]:
                # print(watered, (start,end))
                watered[-1] = [start, end]
            else:
                watered.append([start, end])
        
        return len(watered) if watered[-1][-1] >= n else -1

class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        dp = [0] + [n+2] * n
        for i, x in enumerate(ranges):
            for j in range(max(i-x+1, 0), min(i+x, n) + 1):
                dp[j] = min(dp[j], dp[max(i-x, 0)] + 1)
        return dp[n] if dp[n] < n+2 else -1

class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        dp = [0] + [n+2] * n
        for i, v in enumerate(ranges):
            for j in range(max(0, i-v+1), min(n, i+v)+1):
                dp[j] = min(dp[j], dp[max(0, i-v)] + 1)
        return dp[n] if dp[n] < n + 2 else -1


class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        def dfs(i):   
            if i == -1: return [0] + [n+2]*n
            dp = dfs(i-1)
            x = ranges[i]
            for j in range(max(i-x, 0), min(i+x, n) + 1):
                dp[j] = min(dp[j], dp[max(i-x, 0)] + 1)
            return dp
                
        dp = dfs(n)
        return dp[n] if dp[n] < n+2 else -1

class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        dp = [0] + [n+2] * n 
        for i in range(len(ranges)):
            x = ranges[i]
            for j in range(max(i-x, 0), min(i+x, n) + 1):
                dp[j] = min(dp[j], dp[max(i-x, 0)] + 1 )
                
        return dp[n] if dp[n] < n+2 else -1

class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        dp = [0] + [n+2] * n
        for i in range(len(ranges)):
            x = ranges[i]
            for j in range(max(i-x+1, 0), min(i+x, n) + 1):
                dp[j] = min(dp[j], dp[max(i-x, 0)] + 1)
        return dp[n] if dp[n] < n+2 else -1

class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        dp = [n+2] * n + [0]
        for i in range(len(ranges)-1, -1, -1):
            x = ranges[i]
            for j in range(max(i-x, 0), min(i+x, n) + 1):
                dp[j] = min(dp[j], dp[min(i+x, n)] +1 )
                
        return dp[0] if dp[0] < n+2 else -1

class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        dp = [0] + [n+2] * n
        def dfs(i):   
            x = ranges[i]
            for j in range(max(i-x, 0), min(i+x, n) + 1):
                dp[j] = min(dp[j], dp[max(i-x, 0)] + 1)
        for i in range(len(ranges)):
            dfs(i)
        return dp[n] if dp[n] < n+2 else -1

class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        # dp[i] min taps to water [0, i]
        # dp[0] = 0
        dp = [0] + [n+2] * n # n+1 is possible value
        for i, v in enumerate(ranges):
            left = max(i-v, 0)
            right = min(i+v, n)
            for j in range(left+1, right+1):
                dp[j] = min(dp[j], dp[max(0, i-v)]+1)
        if dp[n] < n+2:
            return dp[n]
        return -1

class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        dp=[n+2]*(n+1)
        dp[0]=0
        for i in range(n+1):
            for j in range(max(0,i-ranges[i])+1, min(n, i+ranges[i])+1):
                dp[j]=min(dp[j], dp[max(0,i-ranges[i])]+1)
        print(dp)
        return dp[-1] if dp[-1]<n+2 else -1

class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        dp = [0] + [n+2] * n
        for i, x in enumerate(ranges):
            for j in range(max(i-x, 0), min(i+x, n) + 1):
                dp[j] = min(dp[j], dp[max(i-x, 0)] + 1)
        return dp[n] if dp[n] < n+2 else -1

class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        dp = [0] + [n+2] * n
        def dfs(i):   
            if i == -1: return [0] + [n+2]*n
            dp = dfs(i-1)
            x = ranges[i]
            for j in range(max(i-x, 0), min(i+x, n) + 1):
                dp[j] = min(dp[j], dp[max(i-x, 0)] + 1)
            return dp
                
        dp = dfs(n)
        return dp[n] if dp[n] < n+2 else -1

class Solution:
    def minTaps(self, n: int, ranges) -> int:
        dp = [0] + [n + 2] * n
        for i, x in enumerate(ranges):
            for j in range(max(i - x + 1, 0), min(i + x, n) + 1):
                dp[j] = min(dp[j], dp[max(0, i - x)] + 1)
        return dp[n] if dp[n] < n + 2 else -1

class Solution:
    def minTaps(self, n, A):
        dp = [0] + [n + 2] * n
        for i, x in enumerate(A):
            for j in range(max(i - x + 1, 0), min(i + x, n) + 1):
                dp[j] = min(dp[j], dp[max(0, i - x)] + 1)
        return dp[n] if dp[n] < n + 2 else -1

class Solution:
    def minTaps(self, n: int, ranges) -> int:
        dp = [0] + [float('inf')] * n
        for i, x in enumerate(ranges):
            for j in range(max(i - x + 1, 0), min(i + x, n) + 1):
                dp[j] = min(dp[j], dp[max(0, i - x)] + 1)
        print(dp)
        return dp[n] if dp[n] != float('inf') else -1

class Solution:
    def minTaps(self, n, A):
        dp = [0] + [n + 2] * n
        for i, x in enumerate(A):
            for j in range(max(i - x + 1, 0), min(i + x, n) + 1):
                dp[j] = min(dp[j], dp[max(0, i - x)] + 1)
        if dp[-1] < n + 2:
            return dp[-1]
        return -1

class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        min_range, max_range, open_taps = 0, 0 ,0
        
        while max_range < n:
            for i, r in enumerate(ranges):
                if i - r <= min_range and i + r >= max_range:
                    max_range = i + r
            
            if min_range == max_range:
                return -1
            open_taps += 1
            min_range = max_range
        
        return open_taps


class Solution:
    def minTaps(self, n, A):
        dp = [0] + [n + 2] * n
        for i, x in enumerate(A):
            for j in range(max(i - x + 1, 0), min(i + x, n) + 1):
                dp[j] = min(dp[j], dp[max(0, i - x)] + 1)
        return dp[n] if dp[n] < n + 2 else -1
            


class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        dp = [0] + [n + 2] * n
        for i, x in enumerate(ranges):
            for j in range(max(i - x + 1, 0), min(i + x, n) + 1):
                dp[j] = min(dp[j], dp[max(0, i - x)] + 1)
        return dp[n] if dp[n] < n + 2 else -1

class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        lowest_missing = 0
        taps = 0
        while lowest_missing < n:
            highest = None
            for (idx, tap) in enumerate(ranges):
                if idx - tap > lowest_missing or idx + tap < lowest_missing + 1:
                    continue
                    
                if highest is None or highest < idx + tap:
                    highest = idx + tap
                
            if highest is None:
                return -1
            
            lowest_missing = highest
            taps += 1
            
        return taps


class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        dp=[sys.maxsize]*(n+1)
        dp[0]=0
        for i in range(n+1):
            for j in range(max(0,i-ranges[i]),(min(n,i+ranges[i]))+1):
                    dp[j]=min(dp[j],1+dp[max(0,i-ranges[i])])
            
        if(dp[n]==sys.maxsize):
            return -1
        return dp[n]
            


class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        dp = [0] + [n+1] * n
        
        for i, x in enumerate(ranges):
            for j in range(max(i- x + 1, 0), min(n,i+x)+ 1):
                dp[j] = min(dp[j], dp[max(0,i-x)]+ 1)
        return dp[n] if dp[n]!=n+1 else -1
        # dp = [0] + [n + 2] * n
        # for i, x in enumerate(ranges):
        #     for j in range(max(i - x + 1, 0), min(i + x, n) + 1):
        #         dp[j] = min(dp[j], dp[max(0, i - x)] + 1)
        # return dp[n] if dp[n] < n + 2 else -1


class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        dp = [0] + [n+2]*n
        for i, r in enumerate(ranges):
            for j in range(max(0, i-r+1), min(n, i+r)+1):
                dp[j] = min(dp[j], dp[max(0, i-r)]+1)
        return dp[n] if dp[n] < n+2 else -1

class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        dp = [0] + [n + 2] * n
        for i, x in enumerate(ranges):
            for j in range(max(i - x + 1, 0), min(i + x, n) + 1):
                dp[j] = min(dp[j], dp[max(0, i - x)] + 1)
        return dp[n] if dp[n] < n + 2 else -1
                    
                
                
            
            
        
                


class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        res = 0
        DP = [float('inf')] * (n+1)
        farest = 0
        DP[0] = 0
        for i, r in enumerate(ranges):
            for x in range(max(i-r, 0), min(i+r+1, n+1)):
                DP[x] = min(DP[x], DP[max(i-r, 0)]+1)
        return DP[-1] if DP[-1] != float('inf') else -1
                
            


class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
#         max_range = [0] * (n + 1)
#         for idx, r in enumerate(ranges):
#             left, right = max(0, idx - r), min(n, idx + r)
#             max_range[left] = max(max_range[left], right - left)
        
#         # it's a jump game now
#         start, end, step = 0, 0, 0
#         while end < n:
#             step += 1
#             start, end = end, max(i + max_range[i] for i in range(start, end + 1))
#             if start == end:
#                 return -1
#         return step
        

        
        dp = [float('inf')] * (n + 1)
        dp[0] = 0
        for idx, r in enumerate(ranges):
            for j in range(max(idx - r + 1, 0), min(idx + r, n) + 1):
                dp[j] = min(dp[j], dp[max(0, idx - r)] + 1)
        return dp[n] if dp[n] < float('inf') else -1
        # dp = [0] + [float('inf')] * n
        # for idx, r in enumerate(ranges):
        #     for j in range(max(idx - r + 1, 0), min(idx + r, n) + 1):
        #         dp[j] = min(dp[j], dp[max(0, idx - r)] + 1)
        # return dp[n] if dp[n] < float('inf') else -1


class Solution:
    
    def minTaps1(self, n: int, ranges: List[int]) -> int:
        intervals = []
        for i in range(n+1):
            if ranges[i]:
                left = max(0, i - ranges[i])
                right = min(n, i + ranges[i])
                intervals.append((left, right))
        intervals.sort()
        res = 0
        max_pos = 0
        prev_max_pos = -1
        for i, j in intervals:
            # max_pos >= n: all range covered
            if max_pos >= n:
                break
            # i > max_pos: [max_pos, i] not covered
            if i > max_pos:
                return -1
            elif prev_max_pos < i <= max_pos: # (i, j) will cover new interval
                res = res + 1
                prev_max_pos = max_pos
                print((i, j), res)
            max_pos = max(max_pos, j)
        return res if max_pos >= n else -1
        
    def minTaps(self, n: int, ranges: List[int]) -> int:
        dp = [0] + [n + 1] * n
        for i, x in enumerate(ranges):
            for j in range(max(i - x + 1, 0), min(i + x, n) + 1):
                dp[j] = min(dp[j], dp[max(0, i - x)] + 1)
        # print(dp)
        return dp[n] if dp[n] < n + 1 else -1

from heapq import heappush, heappop 
class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
                
        taps_by_start = []  # ranked by start
        for i, r in enumerate(ranges):
            if r != 0:
                tap = (max(0, i-r), i+r) # start, end
                heappush(taps_by_start, tap)
        # print(taps_by_start)

        taps_by_end = [] # the largest end at top 
        current_min = 0
        num_of_pipe= 0
        
        while current_min < n:
            while taps_by_start and taps_by_start[0][0] <= current_min:
                tap = heappop(taps_by_start)
                tap_reverse = (-tap[1], tap[0])
                heappush(taps_by_end, tap_reverse)

            if taps_by_end:
                next_pipe = heappop(taps_by_end)  # -end, start
                current_min = - next_pipe[0]
                num_of_pipe +=1 
            else: 
                return -1 
        
        return num_of_pipe 
         


#[Runtime: 1212 ms, faster than 5.27%] DP
#O(N * 200)
#f(i): the minimum number of taps that we can cover range: 0~i and i is opended
#Since 0~n is already sorted sequence of number
#f(i) = 1 if ranges[i][BEGIN] <= 0
#f(i) = min( f(j) where max(0, ranges[i][BEGIN]-100) <= j < i and ranges[j][END] >= ranges[i][BEGIN] ) + 1
#NOTE: WA: return min { f(i) if i + ranges[i][END] >= n }
from math import inf
class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        dp = [inf] * (n+1)
        for i in range(n+1):
            if not ranges[i]:
                continue #skip impossible tapes to prevent from empty arg of `min`
            s = i - ranges[i]
            if s <= 0:
                dp[i] = 1
            else:
                dp[i] = 1 + min([dp[j] for j in range(max(0, s - 100), i) if ranges[j] and j + ranges[j] >= s] + [inf])
        res = min([dp[i] for i in range(n+1) if ranges[i] and i + ranges[i] >= n] + [inf])
        return res if res != inf else -1

class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        min_range, max_range, open_taps, idx = 0, 0 ,0, 0
        
        while max_range < n:
            for i in range(len(ranges)):
                if i - ranges[i] <= min_range and i + ranges[i] >= max_range:
                    max_range = i + ranges[i]
            
            if min_range == max_range:
                return -1
            open_taps += 1
            min_range = max_range
        
        return open_taps


class Solution:
    def minTaps(self, n, A):
        dp = [0] + [n + 2] * n
        for i, x in enumerate(A):
            left = i- x
            right = i+x
            for j in range(max(left+1, 0), min(right, n) + 1):
                dp[j] = min(dp[j], dp[max(0, left)] + 1)
        return dp[n] if dp[n] < n + 2 else -1

class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        
        dp = [n+2 for i in range(n+1)]
        dp[0] = 0
        
        for i, r in enumerate(ranges):
            for j in range(max(0, i-r), min(len(ranges), i+r+1)):
                dp[j] = min(dp[j], dp[max(0, i-r)] + 1)
        
        print(dp)
        return dp[-1] if dp[-1] < n+2 else -1


class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        dp = {i: 2*n for i in range(n+1)}
        dp[0] = 0
        for i in range(0, n+1):
            for j in range(max(0, i-ranges[i]), min(n+1, i+ranges[i]+1)):
                dp[j] = min(dp[j], dp[max(0, i-ranges[i])] + 1)
        # print(dp)
        return dp[n] if dp[n] < 2*n else -1

class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        dp = [0] + [n+2] * n
        for i, value in enumerate(ranges):
            for j in range(max(i-value,0), min(i+value, n) + 1):
                dp[j] = min(dp[j], dp[max(i-value, 0)] + 1)
    
        return dp[n] if dp[n] < n+2 else -1

class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        farthestRightAt = [-1] * (n+1)
        for i, r in enumerate(ranges):
            if r == 0:
                continue
            left = i-r
            right = i+r
            for j in range(max(0, left), min(right+1, n+1)):
                farthestRightAt[j] = min(n, max(farthestRightAt[j], right))
                
        if -1 in farthestRightAt:
            return -1
        i = 0
        count = 0
        while i < n:
            i = farthestRightAt[i]
            count += 1
        return count

class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        
        sorted_ranges = ([(max(0,i-v), min(n, i+ v)) for i,v in enumerate(ranges)])
        dicts = {}
        for i in sorted_ranges:
            dicts[i[0]] = max(i[1], dicts.get(i[0], -10e9))
        
        reduced_ranges = sorted([(k,v) for k, v in dicts.items()])
        
        
        prev_max = max_e = reduced_ranges[0][1]
        min_start = reduced_ranges[0][0]
        
        
        taps = 1
        i = 0
        s,e = reduced_ranges[i]
        print(reduced_ranges)
        
        while max_e < n:
            # print(\"cluster\", s, e, prev_max, \"reached to \" ,max_e, \"with\" , taps)
            taps += 1
            while True:
                s,e = reduced_ranges[i + 1]
                
                if s > prev_max: 
                    # print(\"break at i\",s,e, i)
                    break
                    
                max_e = max(e, max_e)
                # print(reduced_ranges[i], \"new_max\", max_e)
                i += 1
                
                
                if max_e >= n:
                    # print(\"last one\")
                    return taps
            
            if max_e == prev_max:
                return -1
            prev_max = max_e
            max_e = max_e
                
        return taps 

class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        taps=[]
        for i in range(len(ranges)):
            taps.append((i-ranges[i],i+ranges[i]))
        
        taps.sort()
        @lru_cache(None)
        def helper(i):
            # minimum number of taps to open if we open i to reach end
            if i>=n+1:return float('inf')
            if taps[i][1]>=n:return 1
            ans=float('inf')
            # lets do binary search here
            
            for j in range(i+1,n+1):
                if taps[j][0]>taps[i][1]:
                    break
                if taps[j][0]<=taps[i][1] and taps[j][1]>taps[i][1]:
                    # benefit of picking this guy
                    ans=min(ans,1+helper(j))
            return ans
        ans=float('inf')
        for i in range(n,-1,-1):
            res=helper(i)
            if taps[i][0]<=0 and res<ans:
                ans=res
        return -1 if ans==float('inf') else ans
                
        
            
        
                    
                    
                    
                
            
        





class Solution:
    def minTaps(self, n, A):
        dp = [0] + [n + 2] * n
        for i, x in enumerate(A):
            for j in range(max(i - x + 1, 0), min(i + x, n) + 1):
                dp[j] = min(dp[j], dp[max(0, i - x)] + 1)
        return dp[n] if dp[n] < n + 2 else -1



# class Solution:
#     def minTaps(self, n: int, ranges: List[int]) -> int:
        
#         covers = sorted([(i - ranges[i], i + ranges[i], i) for i in range(n + 1) if ranges[i]], key=lambda x: (x[0], -x[1]))
#         print(covers)
#         cnt = 0
#         most_right = float('-inf')
#         lst = []
#         for curr_left, curr_right, curr_idx in covers:
#             if curr_right > most_right:
#                 most_right = curr_right
#                 cnt += 1
#                 lst.append(curr_idx)
#         print(cnt)
#         return cnt if most_right >= n else -1



class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        stack = []
        for i in range(n + 1):
            l, r = i - ranges[i], i + ranges[i]
            if not stack or (l <= 0 and r >= stack[-1]):
                stack = [r]
            elif l <= stack[-1] < r:
                while len(stack) > 1:
                    prev = stack.pop()
                    if l > stack[-1]:
                        stack.append(prev)
                        break
                stack.append(r)
            if stack[-1] >= n:
                return len(stack)
        return -1

class Solution: #DP
    def minTaps(self, n, A):
        dp = [0] + [n + 2] * n
        for i, x in enumerate(A):
            for j in range(max(i - x + 1, 0), min(i + x, n) + 1):
                dp[j] = min(dp[j], dp[max(0, i - x)] + 1)
        return dp[n] if dp[n] < n + 2 else -1



# class Solution:
#     def minTaps(self, n: int, ranges: List[int]) -> int:
        
#         covers = sorted([(i - ranges[i], i + ranges[i], i) for i in range(n + 1) if ranges[i]], key=lambda x: (x[0], -x[1]))
#         print(covers)
#         cnt = 0
#         most_right = float('-inf')
#         lst = []
#         for curr_left, curr_right, curr_idx in covers:
#             if curr_right > most_right:
#                 most_right = curr_right
#                 cnt += 1
#                 lst.append(curr_idx)
#         print(cnt)
#         return cnt if most_right >= n else -1


class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        # 傻瓜一点想法  DP 
        # 每个点 左边loop 当前最小值和左边最小值+1
        # 有点每个点  同理
       
        dp = [0] + [n + 2] * n
        for i , cur in enumerate(ranges):
            for j in range(max(0,i-cur+1),min(n,i+cur)+1):
                dp[j] = min(dp[j], dp[max(0,i-cur)] + 1)
        return dp[n] if dp[n] < n + 2 else -1       # 0-5 最多有6个 n+1

class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        minimum=0
        maximum=0
        total=0
        while maximum<n:
            for i in range(len(ranges)):
                left=i-ranges[i]
                right=i+ranges[i]
                if left<=minimum and right>maximum:
                    maximum=right
            if minimum==maximum:
                return -1
            minimum=maximum
            total+=1
        return total

class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        
        
        
        ranges = [[i-val, i+val] for i, val in enumerate(ranges)]
        ranges.sort()
        
        print(ranges)
        max_reach = 0
        i = 0 
        taps=0
        
        while max_reach <n:
            curr_reach = 0
            if max_reach == 6:
                print(3)
            while i < n+1 and ranges[i][0] <= max_reach:
                curr_reach = max(curr_reach, ranges[i][1])
                i += 1
            
            print(curr_reach , max_reach)
            if curr_reach <= max_reach:
                return -1
            
            max_reach = curr_reach
            taps += 1
        
        return taps

class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        windows = []

        for i, range in enumerate(ranges):
            windows.append((max(0, i-range), i+range))
        
        windows.sort()
        
        i = 0
        max_water = 0
        num_taps = 0
        
        while i < len(windows):
            if max_water >= n:
                return num_taps
            
            num_taps += 1
            prev_water = max_water
            j = i
            
            while j < len(windows) and windows[j][0] <= prev_water:
                if windows[j][1] > max_water:
                    max_water = windows[j][1]
                    
                j += 1
            
            if max_water == prev_water:
                break
            
            i = j
        
        return -1 if max_water < n else num_taps

# 1326. Minimum Number of Taps to Open to Water a Garden

def redundant (a, b):
    (al, ar), (bl, br) = a, b
    return al <= bl <= br <= ar or bl <= al <= ar <= br

def union (a, b):
    (al, ar), (bl, br) = a, b
    return (min (al, bl), max (ar, br))

def remove_overlap (ranges):
    ans = []
    for rng in ranges:
        ans.append (rng)
        while len (ans) >= 2 and redundant (ans[-2], ans[-1]):
            b = ans.pop (); a = ans.pop ()
            ans.append (union (a, b))
    return ans

def union_covers (a, b, c):
    (al, ar), (bl, br), (cl, cr) = a, b, c
    return al <= cl <= ar <= cr and al <= bl <= br <= cr

def min_taps (n, radii):
    assert n >= 1
    assert len (radii) == n + 1
    
    ranges = []
    for (center, radius) in enumerate (radii):
        if radius > 0:
            left_end = max (0, center - radius)
            right_end = min (n, center + radius)
            ranges.append ((left_end, right_end))

    ranges = remove_overlap (ranges)

    final_ranges = []
    for rng in ranges:
        if len (final_ranges) >= 2 and union_covers (final_ranges[-2], final_ranges[-1], rng):
            final_ranges.pop ()
        final_ranges.append (rng)

    if final_ranges and final_ranges[0][0] == 0 and final_ranges[-1][-1] == n and all (final_ranges[i][1] >= final_ranges[i+1][0] for i in range (len (final_ranges) - 1)):
        return len (final_ranges)
    else:
        return -1


class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        return min_taps(n, ranges)

class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        covers = []
        for i,r in enumerate(ranges):
            if r==0:
                continue
            covers.append([max(0,i-r), min(n, i+r)])
        
        if len(covers)==0:
            return -1
        
        covers.sort(key=lambda x:x[0])        
        
        result = 0
        reach = 0
        while len(covers)!=0:
            temp = None
            while len(covers)!=0:
                if covers[0][0] - reach>0:
                    break
                x = covers.pop(0)
                if temp==None or temp[1]<x[1]:
                    temp = x
         
            if temp is None:
                return -1
            result+=1
            reach = temp[1]
            if reach==n:
                break
            
        return result
                    
                
    
    


#[] Greedy
#O(NlogN)
BEGIN, END = 0, 1
class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        stitch = max_reach = cnt = i = 0
        clips = sorted((i-diff, i+diff) for i, diff in enumerate(ranges) if diff) #sort by start
        N = len(clips)
        while max_reach < n: #NOTE: WA: max_reach < `n` instead of `N`
            #try to find furthest end-point
            while i < N and clips[i][BEGIN] <= stitch:
                max_reach = max(max_reach, clips[i][END])
                i += 1
            if stitch == max_reach:
                return -1 #unable to reach n
            cnt += 1
            stitch = max_reach #put clips[i] into solution and extend the next end-point
        return cnt

class Solution:
    # def minTaps(self, n: int, ranges: List[int]) -> int:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        opens, closes, closed = [[] for _ in range(n)], [[] for _ in range(n)], set()
        for i in range(len(ranges)):
            idx = 0
            if i - ranges[i] > 0:
                idx = i - ranges[i] 
            if idx < len(opens):
                opens[idx].append(i)
            if i + ranges[i] < n:
                closes[i + ranges[i]].append(i)
        heap, cur_open_tap, res = [], None, 0
        for i in range(n):
            for op in opens[i]:
                heappush(heap, [-(op + ranges[op]), op])
            for cl in closes[i]:
                closed.add(cl)
                if cl == cur_open_tap:
                    cur_open_tap = None
            while cur_open_tap is None:
                if not heap:
                    return -1
                if heap[0][1] in closed:
                    heappop(heap)
                else:
                    cur_open_tap = heap[0][1]
                    res += 1
        return res

class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        max_right = [0] * (n + 1)
        
        for i,x in enumerate(ranges):
            max_right[max(0, i - x)] = max(max_right[max(0, i - x)], i + x)
        
        i = 0
        best_right = 0
        ans = 0
        j = 0
        
        while i < n:
            while j <= i:
                best_right = max(max_right[j], best_right)
                j += 1

            if best_right <= i:
                return -1 
            
            ans += 1
            i = best_right
            
                
            
        return ans


class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        r, R = 0, sorted([x-r, x+r] for x, r in enumerate(ranges)) + [[9**9]]
        did = can = count = 0
        for x in range(n):
            while R[r][0] <= x:
                can = max(can, R[r][1])
                r += 1
            if did == x:
                if can <= x:
                    return -1
                did = can
                count += 1
                if did == n:
                    break
        return count


class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        taps = []
        for i, r in enumerate(ranges):
            if r > 0:
                taps.append([max(0, i - r), -min(n, i + r)])
        if not taps:
            return -1
        taps.sort()
        if taps[0][0] != 0:
            return -1
        stack = [[taps[0][0], abs(taps[0][1])]]
        
        #print(taps)

        for t in taps[1:]:
            if stack[-1][1] == n:
                break
            l, r = t[0], abs(t[1])
            if r <= stack[-1][1]:
                continue
            if l > stack[-1][1]:
                return - 1
            if len(stack) == 1:
                stack.append([l, r])
            else:    
                if l <= stack[-2][1]:
                    stack.pop()
                stack.append([l, r])

        #print(stack)
        return len(stack)


class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        
        needed = [100000]*(n+1)
        
        for i in range(len(ranges)):
            #print(needed)
            l_i = i - ranges[i]
            
            if l_i <= 0:
                need = 1
            else:
                need = needed[l_i] + 1
                
            right_most = min(i + ranges[i],len(ranges)-1)
            
            while need < needed[right_most] and right_most > i-1:
                needed[right_most] = need
                right_most -= 1
        
        if needed[-1]>10000:
            return -1

        return needed[-1]

class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        steps = [0]*(n+1)
        for i, r in enumerate(ranges):
            if i - r < 0:
                steps[0] = max(i + r, steps[0])
            else:
                steps[i - r] = max(i + r, steps[i - r])
        #print(steps)
        
        num = 1
        cur = 0
        cur_max = steps[0]
        while cur_max < n:
            next_max = cur_max
            for loc in range(cur + 1, cur_max + 1):
                next_max = max(next_max, steps[loc])
            #print(cur, cur_max, next_max)
            if next_max == cur_max:
                return -1
            num += 1
            cur = cur_max
            cur_max = next_max
        return num

class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        for i, val in enumerate(ranges):
            if i - val < 0:
                ranges[0] = max(i + val, ranges[0])
            else:
                ranges[i - val] = max(val * 2, ranges[i - val])
        i = 0
        prev = -1
        counter = 0
        while i != prev:
            distance = ranges[i]
            if i + distance >= n:
                return counter + 1
            maxIndex = i
            for j in range(i+1, i + distance + 1):
                if j + ranges[j] >= maxIndex + ranges[maxIndex]:
                    maxIndex = j
                j += 1
            prev = i
            i = maxIndex
            counter += 1
        return -1



class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        ls = []
        for i in range(n+1): 
            ls.append((max(i-ranges[i],0),min(i+ranges[i],n+1)))
        ls.sort(key = lambda x:(x[0],-x[1]))
        ans,a,b = 0,-1,0
        while b < n:
            c,d = ls.pop(0)
            if c > b: return -1
            elif d <= b: continue
            elif c > a:
                ans += 1
                a,b = b,d
            elif c <= a:
                b = d
        return ans


class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        # max_right from each point
        max_right = [0] * (n+1)
        for i, x in enumerate(ranges):
            l = max(0, i-x)
            r = min(n, i+x)
            max_right[l] = r
        # jump game
        ans = 0
        curr_reach = max_reach = 0
        print(max_right)
        for i in range(n+1):
            max_reach = max(max_reach, max_right[i])
            if i == curr_reach:
                print((i, curr_reach, max_reach))
                curr_reach = max_reach
                ans += 1
                if curr_reach == n:
                    return ans
        return ans if curr_reach >= n else -1


class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        
        for i, r in enumerate(ranges):
            left = max(0, i-r)
            right = i+r
            ranges[left] = max(ranges[left], right)
            
        r, res = 0, 0
            
        while r < n:
            tmp = r
            r = max(ranges[0:r+1])
            res += 1
            if tmp == r:
                return -1
    
        return res


class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        if n == 0:
            return 0
        
        steps = [0] * (n + 1)
        for i, r in enumerate(ranges):
            left = max(0, i - r)
            right = min(n, i + r)
            for j in range(left, right+1):
                steps[j] = right
        
        #print(steps)
        res = 1
        prev = 0
        cur = steps[0]
        while cur > prev:
            if cur == n:
                return res
            
            tmp = cur
            for i in range(prev+1, cur+1):
                cur = max(cur, steps[i])
            
            prev = tmp
            res += 1
        
        return -1


class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        
        for i, r in enumerate(ranges):
            left = max(0, i-r)
            right = i+r
            ranges[left] = max(ranges[left], right)
            
        l, r, res = 0, 0, 0
            
        while r < n:
            jump = max(ranges[l:r+1])
            if r == jump:
                return -1
            res += 1
            l, r = r, jump
    
        return res


class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        l=[]
        for i in range(n+1):
            l.append((i-ranges[i], i+ranges[i]))
        l.sort()
        maxlen=0
        curpos=0
        res=0
        while maxlen<n:
            new=maxlen
            while curpos<=n and l[curpos][0]<=maxlen:
                if l[curpos][1]>maxlen:
                    new=max(new, l[curpos][1])
                curpos+=1  
            if maxlen==new:
                return -1
            res+=1
            maxlen=new
        return res     


class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        
        
        max_range = [0 for i in range(n+1)]
        
        for i in range(n+1):
            
            left, right = max(0,i-ranges[i]), min(i+ranges[i], n)
       
            max_range[left] = max(max_range[left], right - left)
          
        jumps = 0
        
        curlen, endlen = 0, 0
        
        print(max_range)
        for i in range(n+1):
            
            if max_range[i] == 0 and endlen < i:
                return -1
            
            curlen = max(curlen, i+max_range[i])
            
            if i == endlen:
                endlen = curlen
                jumps += 1
            
            if endlen == n:
                return jumps
                
        return jumps

class Solution:
    def minTaps(self, n: int, ranges):
        taps = [[max(0, i - ranges[i]), min(n, i + ranges[i])] for i in range(n + 1)]
        taps.sort()
        ans = i = last = 0

        while i < len(taps):
            if last == n:
                return ans

            if taps[i][0] > last:
                return -1 if last < n else ans

            temp = -1

            while i < len(taps) and taps[i][0] <= last:
                temp = max(temp, taps[i][1])
                i += 1

            if temp > last:
                ans += 1
                last = temp
            else:
                return -1

        return ans if last == n else -1

class Solution:
    def minTaps(self, n: int, minjump: List[int]) -> int:
        
        
        for i in range(n+1):
            left= max(0, i-minjump[i])
            right= min(n, i+minjump[i])
            minjump[left]=max(minjump[left],right-left)
        # print(minjump)
        jump=1
        steps=minjump[0]
        maxreach=minjump[0]
        lastindex,maxjump=0,minjump[0]
        for i in range(1,n+1):
            steps-=1
            if steps<0:
                return -1
            
            if i+minjump[i]>maxreach:
                maxreach=minjump[i]+i
                maxjump=minjump[i]
                lastindex=i
            if steps==0 and i!=n:
                steps= lastindex+maxjump-i
                jump+=1
        return jump

class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        
        for i, r in enumerate(ranges):
            if r > 0:
                left = max(0, i-r)
                right = i+r
                ranges[left] = max(ranges[left], right)
            
        r, res = 0, 0
            
        while r < n:
            tmp = r
            r = max(ranges[0:r+1])
            res += 1
            if tmp == r:
                return -1
    
        return res


class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        new_ranges = []
        for i in range(len(ranges)):
            new_ranges.append([max(0, i-ranges[i]), min(n, i+ranges[i])])
            
        new_ranges = sorted(new_ranges, key=lambda x: x[0])    
        
        tap_counter = 0
        ranges_counter = 0
        i = 0
        while i < n:
            # Find all ranges with a start value lower than the current_counter
            max_right = -1
            while ranges_counter < len(new_ranges) and new_ranges[ranges_counter][0] <= i:
                max_right = max(max_right, new_ranges[ranges_counter][1])
                ranges_counter += 1
                
            if max_right == -1:
                return -1
            
            tap_counter += 1
            
            i = max_right
            
        return tap_counter    

class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        if len(ranges) == 0: return 0
        
        segments = [(max(0, index - num), min(n, index + num)) for index, num in enumerate(ranges)]
        segments = sorted(segments)
        left, right = -1, 0
        cnt = 0
        for a, b in segments:
            if a > right: break
                
            # very important
            if right == n: break  # there are segments with [n, n], we don't want to count it again.
            
            if right >= a > left:
                cnt += 1
                left = right
            
            right = max(right, b)
            
        if right == n: return cnt
        return -1

class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        hp = []
        
        for i, r in enumerate(ranges):
            if r != 0:
                heapq.heappush(hp, (max(i-r, 0), -(i+r)))
        #1-5,-2-6, 3-7, 4-8
        ans = []
        while hp:
            start, end = heapq.heappop(hp)
            end = -end
            if not ans:
                ans.append((start, end))
            else:
                #Not overlapped
                if start > ans[-1][1]:
                    return -1
                
                #Already covered
                if end <= ans[-1][1]:
                    continue

                if len(ans) >= 2 and start <= ans[-2][1]:
                    ans[-1] = (start, end)
                elif start <= ans[-1][1]:
                    ans.append((start, end))
                #print(\"here\")
                #print(ans)
            if ans and ans[-1][1] >= n:
                break
        
        print(ans)
        return len(ans) if ans and ans[-1][1] >= n else -1


import bisect
class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        uc = 0
        taps = []
        taps_r = []
        for idx, r in enumerate(ranges):
            if r > 0:
                tap = (idx-r if idx-r>0 else 0, idx+r)
                tapr = (idx+r, idx-r if idx-r>0 else 0)
                taps_r.append(tapr)
                taps.append(tap)
        if not taps:
            return -1
        taps.sort()
        curr_idx = bisect.bisect_left(taps,(1,0))-1
        curr_idx = curr_idx if curr_idx > 0 else 0
        if taps[curr_idx][0] > 0:
            return -1
        e_range = taps[curr_idx][1]
        res = 1
        if e_range>=n:
            return 1
        lo = curr_idx
        hi = len(taps)
        while e_range < n:
            hi = bisect.bisect_left(taps, (e_range+1, 0), lo, hi)
            print(hi)
            max_e = 0
            for i in range(lo,hi):
                if taps[i][1] > max_e:
                    curr_idx = i
                    max_e = taps[i][1]
            if max_e <= e_range:
                return -1
            e_range = max_e
            lo = curr_idx
            hi = len(taps)
            res += 1
        return res


class Solution:
    def minTaps(self, n: int, ranges) -> int:

        def process_input(ranges):
            spans = []
            for i in range(len(ranges)):
                spans.append([max(i - ranges[i], 0), i + ranges[i]])

            return spans

        spans = process_input(ranges)

        spans.sort(key=lambda time: (time[0], -time[1]))

        sol = []
        step = .5
        for i in range(len(spans)):

            if step > n:
                continue

            if spans[i][0] < step and spans[i][1] > step:
                try:
                    if spans[i][0] <= sol[-2][1]:
                        sol.pop()
                except:
                    pass
                sol.append(spans[i])
                step = spans[i][1] + .5



        if step < n:
            return -1
        return len(sol)

class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        items = []
        for i, num in enumerate(ranges):
            items.append((max(0, i - num), min(i + num, n)))
        res = 0
        right = 0
        items.sort()
        i = 0
        while i < len(items):
            farreach = right
            while i < len(items) and items[i][0] <= right:
                farreach = max(farreach, items[i][1])
                i += 1
            
            if farreach == right:
                return -1
            res += 1
            if farreach >= n:
                return res
            right = farreach
        
        return -1

from typing import List, Tuple
from sortedcontainers import SortedSet


class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        # print('-----')
        # print(f'n: {n}')
        # print(f'ranges: {ranges}')

        intervals = SortedSet()

        for i, w in enumerate(ranges):
            newInterval = (max(i - w, 0), min(i + w, n))
            idx = intervals.bisect_left(newInterval)

            if idx < len(intervals) and self.aContainsB(intervals[idx], newInterval):
                continue
            elif idx > 0 and self.aContainsB(intervals[idx-1], newInterval):
                continue
            else:
                change = True
                while change:
                    change = False
                    idx = intervals.bisect_left(newInterval)
                    if idx < len(intervals) and self.aContainsB(newInterval, intervals[idx]):
                        del intervals[idx]
                        change = True
                    elif idx > 0 and self.aContainsB(newInterval, intervals[idx-1]):
                        del intervals[idx-1]
                        change = True
                    elif idx > 1 and self.overlaps(newInterval, intervals[idx-2]):
                        del intervals[idx-1]
                        change = True
                intervals.add(newInterval)

        # print(f'intervals={intervals}')

        prevEnd = 0
        for (start, end) in intervals:
            if start > prevEnd:
                return -1
            prevEnd = end
        if end < n:
            return -1

        return len(intervals)

    def aContainsB(self, a: Tuple[int, int], b: Tuple[int, int]) -> bool:
        a_start, a_end = a
        b_start, b_end = b
        return a_start <= b_start and a_end >= b_end

    def overlaps(self, a: Tuple[int, int], b: Tuple[int, int]) -> bool:
        a_start, a_end = a
        b_start, b_end = b
        return a_end >= b_start and b_end >= a_start


class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        # Start at 6:00PM
        # Get ranges
        import heapq
        print(len(ranges))
        range_tuples = []
        for i, val in enumerate(ranges):
            if val == 0:
                continue
            range_tuples.append((max(0, i - val), min(n, i + val)))
        
        range_tuples = sorted(range_tuples)
                
        heap = [(0, 0)]
        
        for (start_pos, end_pos) in range_tuples:
            # Remove elements from the heap less than start_pos
            while heap and heap[0][0] < start_pos:
                heapq.heappop(heap)
            
            curr_min_cost = float('inf')
            while heap and heap[0][0] == start_pos:
                cost = heapq.heappop(heap)[1]
                if cost < curr_min_cost:
                    curr_min_cost = cost
            
            if curr_min_cost == float('inf'):
                # Get the next closest point cost
                if not heap:
                    return -1
            else:
                heapq.heappush(heap, (start_pos, curr_min_cost))
            curr_min_cost = min([a for (_, a) in heap])
            heapq.heappush(heap, (end_pos, curr_min_cost + 1))
        
        while heap and heap[0][0] < n:
            heapq.heappop(heap)
        
        min_cost = float('inf')
        
        while heap and heap[0][0] == n:
            cost = heap[0][1]
            if cost < min_cost:
                min_cost = cost
            heapq.heappop(heap)
        
        if min_cost == float('inf'):
            return -1
        return min_cost

class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        # max_right from each point
        max_right = [0] * (n+1)
        for i, x in enumerate(ranges):
            l = max(0, i-x)
            r = min(n, i+x)
            max_right[l] = r
        # jump game
        ans = 0
        reach = 0
        while reach < n:
            max_reach = max(r for r in max_right[:reach+1])
            if max_reach <= reach:
                return -1
            reach = max_reach
            ans += 1
        return ans


class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        min_range, max_range, open_taps, idx = 0, 0 ,0, 0
        
        while max_range < n:
            for i in range(idx, len(ranges)):
                if i - ranges[i] <= min_range and i + ranges[i] >= max_range:
                    max_range = i + ranges[i]
                    idx = i
            
            if min_range == max_range:
                return -1
            open_taps += 1
            min_range = max_range
        
        return open_taps


class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        open_ranges = sorted([(idx-span, idx+span) for idx, span in enumerate(ranges)])
        start, end, count = 0, 0, 0
        i = 0
        while i < len(ranges):
            for j in range(i, len(ranges)):
                l, r = open_ranges[j]
                if l <= start:
                    if r >= end:
                        end = r
                        i = j
            count += 1
            if end >= n:
                return count
            if start == end:
                return -1
            start = end


class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        open_ranges = sorted([(idx-span, idx+span) for idx, span in enumerate(ranges)])
        start, end, count = 0, 0, 0
        i = 0
        while i < len(ranges):
            for j in range(i, len(ranges)):
                l, r = open_ranges[j]
                if l <= start:
                    if r >= end:
                        end = r
                        i = j
            count += 1
            if end >= n:
                return count
            if start == end:
                return -1
            start = end
                        


class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        max_right = [0]*(n+1)
        
        for i,r in enumerate(ranges):
                max_right[max(0,i-r)] = max(max_right[max(0,i-r)],min(n,i+ranges[i]))
        dp = [float('inf')]*len(max_right)
        dp[0] = 0
        for i, x in enumerate(ranges):
            for j in range(i+1,max_right[i]+1):
                dp[j] = min(dp[j], dp[i] + 1)
        return dp[n] if dp[n] != float('inf') else -1
        


# 思路
# 贪心策略，我们尽量找到能够覆盖最远（右边）位置的水龙头，并记录它最右覆盖的土地。

# 我们使用 furthest[i] 来记录经过每一个水龙头 i 能够覆盖的最右侧土地。
# 一共有 n+1 个水龙头，我们遍历 n + 1 次。
# 对于每次我们计算水龙头的左右边界，[i - ranges[i], i + ranges[i]]
# 我们更新左右边界范围内的水龙头的 furthest
# 最后从土地 0 开始，一直到土地 n ，记录水龙头数目


# 复杂度分析

# 时间复杂度：时间复杂度取决 l 和 r，也就是说取决于 ranges 数组的值，假设 ranges 的平均大小为 Size 的话，那么时间复杂度为 $O(N * Size)$。

# 空间复杂度：我们使用了 furthest 数组， 因此空间复杂度为 $O(N)$。


class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        furthest, cnt, cur = [0] * n, 0, 0  #做initialization

        for i in range(n + 1):
            l = max(0, i - ranges[i])  #左边最远到哪里
            r = min(n, i + ranges[i])  #n是自己
            for j in range(l, r):   #在左右两边，表示右边能到的最远的地方，
                furthest[j] = max(furthest[j], r)  #经过这个水龙头最多能走到哪里，跟自己无关（没那么有关），跟经过我最远到哪里有关系
        while cur < n:  #从头到尾扫一遍，看看有米有没灌溉到的地方
            if furthest[cur] == 0: return -1
            cur = furthest[cur]  # 比这个数值小的都是能扫到的部分，所以可以直接跳过去
            cnt += 1
        return cnt  #左边有问题的话会-1


class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        intervals = []
        for i, r in enumerate(ranges):
            intervals.append((i - r if i - r > 0 else 0, i + r))
        
        intervals.sort(key=lambda t: (t[0], -t[1]))
        l = len(intervals)
        
        i = 0
        ans = 1
        while i < l:
            if intervals[i][1] >= n:
                return ans
            right = -1
            next_i = -1
            for j in range(i + 1, l):
                if intervals[j][0] <= intervals[i][1] and intervals[j][1] >= right:
                    right = intervals[j][1]
                    next_i = j
            
            if next_i == -1:
                return -1
            
            ans += 1
            i = next_i
            
        return ans

class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
#         taps=[]
#         for i in range(len(ranges)):
#             taps.append((i-ranges[i],i+ranges[i]))
        
#         taps.sort()
#         @lru_cache(None)
#         def helper(i):
#             # minimum number of taps to open if we open i to reach end
#             if i>=n+1:return float('inf')
#             if taps[i][1]>=n:return 1
#             ans=float('inf')
#             # lets do binary search here
#             start=i+1
#             end=n
#             lastindex=-1
#             # get the last index which is smaller than taps[i][1]
#             while start<=end:
#                 mid=start+(end-start)//2
#                 if taps[mid][0]<=taps[i][1]:
#                     lastindex=mid
#                     start=mid+1
#                 else:
#                     end=mid-1
#             if lastindex==-1:return ans
#             for j in range(i+1,lastindex+1):
#                 if taps[j][0]>taps[i][1]:
#                     break
#                 if taps[j][0]<=taps[i][1] and taps[j][1]>taps[i][1]:
#                     # benefit of picking this guy
#                     ans=min(ans,1+helper(j))
                    
#             # sequential code to do that
#             # dont go for binary unless interviewer say so
#             # ask him in the approach if he wants to
            
#             # for j in range(i+1,n+1):
#             #     if taps[j][0]>taps[i][1]:
#             #         break
#             #     if taps[j][0]<=taps[i][1] and taps[j][1]>taps[i][1]:
#             #         # benefit of picking this guy
#             #         ans=min(ans,1+helper(j))
#             return ans
#         ans=float('inf')
#         for i in range(n,-1,-1):
#             res=helper(i)
#             if taps[i][0]<=0 and res<ans:
#                 ans=res
#         return -1 if ans==float('inf') else ans
    
        best = [float('inf') for _ in ranges]
        for i, r in enumerate(ranges):
            if r > 0:
                start, end = i - r, i + r 
                best_with = 1 + (best[start] if start > 0 else 0)
                for j in range(max(0, start), min(len(ranges), end+1)):
                    best[j] = min(best[j], best_with)
        if any(v for v in best if v == float('inf')):
            return -1 
        return best[-1]
                
        
            
        
                    
                    
                    
                
            
        


class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        max_right = [0]*(n+1)
        
        for i,r in enumerate(ranges):
                max_right[max(0,i-r)] = max(max_right[max(0,i-r)],min(n,i+ranges[i]))
        dp = [float('inf')]*len(max_right)
        dp[0] = 0
        for i, x in enumerate(ranges):
            for j in range(i+1,max_right[i]+1):
                dp[j] = min(dp[j], dp[i] + 1)
        return dp[n] if dp[n] < n + 2 else -1

class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        if n < 1 or ranges is None: return -1
        dp = [None]*len(ranges)
        # for each tap
        for i in range(len(dp)):
            # calc tap left and right extent
            l = max(0, i-ranges[i])
            r = min(len(dp)-1, i+ranges[i])
            # for each cell in extent, take the min of the cell or the left extent of the tap
            for j in range(l, r+1):
                if dp[j] is None:
                    dp[j] = l
                else:
                    dp[j] = min(dp[j], l)
            # since we can reach to front from last, only one tap is required
            if dp[-1] == 0:
                return 1
        # start from end, jump backwards incrementing tap count each time
        # careful to exit if no jump can be made
        i = len(dp)-1
        c = 0
        while i > 0 and dp[i] is not None and dp[i] != i:
            i = dp[i]
            c += 1
        # if we can jump all the way to the front, then return the count else -1
        return c if i == 0 else -1

class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        inf = 1 << 50
        prev = collections.defaultdict(lambda: inf)
        for i, r in enumerate(ranges):
            prev[min(i+r, n)] = min(prev[min(i+r, n)],max(i-r,0))
 
        dp = [inf] * (n + 1)
        dp[0] = 0
 
        for x in range(n+1):
            for y in range(prev[x], x):
                dp[x] = min(dp[y] + 1, dp[x])
 
        res = dp[n]
        if res >= inf:
            return -1
 
        return res

class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        dp=[sys.maxsize]*(n+1)
        dp[0]=0
        for i in range(n+1):
            l=max(0,i-ranges[i])
            r=min(n,i+ranges[i])
            
            for j in range(l,r+1):
                    dp[j]=min(dp[j],1+dp[l])
                
        if(dp[n]==sys.maxsize):
            return -1
        return dp[n]
            


class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        '''        
        # top-down TLE
        dp = [0] + [float('inf')]*n
        def helper(k):
            if not (1<= k <= n):
                return 0
            if dp[k]!=float('inf'):
                return dp[k]
            dp[k] = min([helper(i-x)+1 for i, x in enumerate(ranges)\\
                      if k in range(i-x+1, i+x+1)] or [-1])
            return dp[k]
        return helper(n)
        '''
        
        if n == 0: 
            return 0
        dp = [0] + [float('inf')]*n
        for i, x in enumerate(ranges):
            start, end = max(0, i-x), min(n, i+x)
            for j in range(start, end+1):
                dp[j] = min(dp[j], dp[start]+1)
        return dp[-1] if dp[-1]!=float('inf') else -1
        
        '''        
        # greedy
        covers = sorted([[i-x, i+x] for i, x in enumerate(ranges)], key = lambda x: (x[0], -x[1]))
        #print(covers)
        res, prev_end, end = 0, -float('inf'), 0
        for src, dest in covers:
            if src > end or end >= n:
                break
            if prev_end < src <= end:
                prev_end, res = end, res + 1
            end = max(end, dest)
        return res if end >= n else -1
        '''

class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        best = [n+1 for _ in ranges]
        for i, r in enumerate(ranges):
            if r > 0:
                start, end = i - r, i + r 
                best_with = 1 + (best[start] if start > 0 else 0)
                for j in range(max(0, start), min(len(ranges), end+1)):
                    best[j] = min(best[j], best_with)
        if any(v for v in best if v == n+1):
            return -1 
        return best[-1]

class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        dp = [float('inf')] * (n+1)
        dp[0] = 0
        for cur in range(n+1):
            left = max(0,cur - ranges[cur] + 1)
            right = min(n,cur+ranges[cur])
            lastend = max(0, cur - ranges[cur])
            for idx in range(left, right+1):
                dp[idx] = min(dp[idx], dp[lastend] + 1)
        return dp[-1] if dp[-1] < float('inf') else -1

class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        dp = [-1 for x in range(n+1)]
        
        for i in range(n+1):
            minId = max(0, i-ranges[i])
            maxId = min(n, i+ranges[i])
            
            for i in range(minId, maxId+1):
                dp[i] = max(dp[i], maxId)
        
        if dp[0] == -1:
            return -1
        
        maxReach = dp[0]
        count = 1
        
        while maxReach < n:
            nxt = dp[maxReach]
            if nxt == maxReach:
                return -1
            maxReach = nxt
            count += 1
        
        return count

class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        # dp[i] min taps to water [0, i]
        # dp[0] = 0
        dp = [0] + [n+2] * n # n+1 is possible value
        for i, v in enumerate(ranges):
            left = max(i-v, 0)
            right = min(i+v, n)
            for j in range(left, right+1):
                dp[j] = min(dp[j], dp[left]+1)
        if dp[n] < n+2:
            return dp[n]
        return -1

class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        full_ranges = []
        for i in range(n + 1):
            r = (i - ranges[i], i + ranges[i])
            full_ranges.append(r)
        
        full_ranges.sort()
        range_idx = 0
        
        covered_max = 0
        num_taps = 0
        
        while covered_max < n and range_idx < len(full_ranges):
            if full_ranges[range_idx][0] > covered_max:
                return -1
            furthest = -1
            while range_idx < len(full_ranges) and full_ranges[range_idx][0] <= covered_max:
                furthest = max(furthest, full_ranges[range_idx][1])
                range_idx += 1
            assert(furthest != -1)
            num_taps += 1
            covered_max = furthest
        
        if covered_max < n:
            return -1
        else:
            return num_taps


class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
             
        max = 0 
        min = 0
        index = 0
        total = 0
        
        while(max<n):
            
            for i in range(index,len(ranges)):
                
                left = i-ranges[i]
                right = i+ranges[i]
                
                if left <= min and right > max:
                    max = right
                    index = i
                    
            if min == max: 
                return -1
            
            total+=1
            
            min = max
            
        return total


class Solution:
    
    
    
    def minTaps(self, n: int, ranges: List[int]) -> int:
                
        rangesCovered = {}
        # key = spot, value = range as tuple
    
    
    
        for i, ran in enumerate(ranges):
            if (ran == 0):
                continue
            rangesCovered[i] = (max(0, i - ranges[i]), min(n, i + ranges[i]))
        
        
        # print(rangesCovered)
        dp = [n + 2] * (n + 1)
        dp[0] = 0
        # dp[i] = min number of taps to water all [0, i]
        
        for curRange in list(rangesCovered.values()):
            # print(curRange)
            startInd = curRange[0]
            endInd = curRange[1]
            for i in range(startInd + 1, endInd + 1):
                dp[i] = min(dp[i], dp[startInd] + 1)
            # print(dp)
        
        
        
        if (dp[n] == (n + 2)):
            return -1
        else:
            return dp[n]
#         taps = []
#         for i in range(n + 1):
#             isCovered[i] = False
#             taps.append(i)
            
        
        
#         curMins = float(\"inf\")
#         def recur(tapsRem, curCount):
#             # print(curCount, tapsRem)
#             # print(isCovered)
#             nonlocal curMins
#             if (all(isCovered.values())):
                
#                 curMins = min(curMins, curCount)
#                 return
#             else:
#                 if (curCount > curMins):
#                     return
                
#                 for i, val in enumerate(tapsRem):
#                     newRem = tapsRem[:i] + tapsRem[i + 1:]
#                     wasFalses = []
#                     for j in range(rangesCovered[i][0], rangesCovered[i][1] + 1):
#                         if isCovered[j] == False:
#                             wasFalses.append(j)
#                         isCovered[j] = True
                    
#                     recur(newRem, curCount + 1)
#                     for ind in wasFalses:
#                         isCovered[ind] = False
                    
#         # print(taps)
#         recur(taps, 0)
#         if (curMins ==  float(\"inf\")):
#             return -1
#         return curMins
        
                
                
                
                
            
            
            
            


class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        # cover[i] shows the list number of taps needed to cover 0-i
        # inf for impossible
        cover = [math.inf] * n
        
        for i, r in enumerate(ranges):
            start = max(i-r, 0)
            end = min(i+r, n)
            
            pre_min = cover[start-1] if start > 0 else 0
            for j in range(start, end):
                cover[j] = min(cover[j], 1+pre_min)
    
        return cover[-1] if cover[-1] != math.inf else -1

class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        dp = [sys.maxsize]*(n+1)
        dp[0]=0
        
        for i,tmp in enumerate (ranges):
            left = max(0,i-tmp)
            right = min(n,i+tmp)
            
            for j in range(left,right+1):
                dp[j]=min(dp[j],dp[left]+1)
        return dp[n] if dp[n]<sys.maxsize else -1

class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        dp = [n+2 for _ in range(n+1)] #minimum number of taps to water i
        dp[0] = 0
        for i, amount in enumerate(ranges):
            left = max(0,i - amount)
            right = min(n, i + amount)
            for j in range(left + 1, right+ 1):
                dp[j] = min(dp[j], dp[left] +1)
        return -1 if dp[n] == n+2 else dp[n]
        


class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        dp = [n+2 for _ in range(n+2)] #minimum number of taps to water i
        dp[0] = 0
        for i, amount in enumerate(ranges):
            left = max(0,i-amount)
            right = min(n, i + amount)
            for j in range(left + 1, right+ 1):
                dp[j] = min(dp[j], dp[left] +1)
        
        return -1 if dp[n] == n+2 else dp[n]
        


class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        dp = [n+2 for _ in range(n + 1)] #min number of water i
        dp[0] = 0
        for i, amount in enumerate(ranges):
            left = max(0, i - amount)
            right = min(n, i + amount)
            for j in range(left, right+1):
                dp[j] = min(dp[j], dp[left] + 1)
        return -1 if dp[n] == n+2 else dp[n] 

class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        rangelist = [None] * (n +1)

        for i in range(n+1):
            s = max(i - ranges[i], 0)
            e = min(i + ranges[i], n)
            
            if rangelist[s] == None:
                rangelist[s] = (s,e)
            else:    
                rangelist[s] = (s, max(rangelist[s][1], e))
        
        curr = mx = 0
        count = 0
        i = 0
        while i < len(rangelist):
            while True and i < len(rangelist): 
                if(rangelist[i] == None):
                    i +=1
                    continue
                s,e = rangelist[i]
                if s > mx: return -1
                if s > curr:
                    break
                mx = max(e,mx)
                i += 1
            if curr != mx:
                curr = mx
                count += 1
            
        if mx < n: return -1
        return count
        


class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        # dp[i] minimum taps required to water garden[:i + 1]
        # for every ranges[i], update dp[i - ranges[i]:i + ranges[i] + 1]
        # when i - ranges[i] - 1 < 0, return 0
        # return -1 when dp[-1] is infinity
        # check if it is possible to have a hole in the middle
        dp = [float('inf')] * (n + 1)
        for i in range(len(ranges)):
            if i - ranges[i] <= 0:
                taps = 1
            else:
                taps = dp[i - ranges[i]] + 1
            
            lo = max(i - ranges[i], 0)
            hi = min(i + ranges[i], n)
            for j in range(lo, hi + 1):
                dp[j] = min(dp[j], taps)
        
        return dp[-1] if dp[-1] != float('inf') else -1


class Solution:
    def minTaps(self, n: int, A: List[int]) -> int:
        dp=[sys.maxsize]*(n+1)
        dp[0]=0
        for i,tap_range in enumerate(A):
            left=max(0,i-tap_range)
            right=min(n,i+tap_range)
            for j in range(left,right+1):
                dp[j]=min(dp[j],dp[left]+1)
        return dp[n] if dp[n]<sys.maxsize else -1
            


class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        dp=[sys.maxsize]*(n+1)
        for i in range(n+1):
            if ranges[i]==0:
                continue
            l=max(0,i-ranges[i])
            r=min(n,i+ranges[i])
            
            for j in range(l,r+1):
                if l==0:
                    dp[j]=1
                else:
                    dp[j]=min(dp[j],1+dp[l])
                
        if(dp[n]==sys.maxsize):
            return -1
        return dp[n]
            


class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        for i, val in enumerate(ranges):
            if i - val < 0:
                ranges[0] = max(i + val, ranges[0])
            else:
                ranges[i - val] = max(val * 2, ranges[i - val])
        i = 0
        prev = -1
        counter = 0
        while i != prev:
            distance = ranges[i]
            if i + distance >= n:
                return counter + 1
            maxIndex = i
            for j in range(i + distance + 1):
                if j + ranges[j] >= maxIndex + ranges[maxIndex]:
                    maxIndex = j
                j += 1
            prev = i
            i = maxIndex
            counter += 1
        return -1



class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        arr=[float('inf') for _ in range(n+1)]
        arr[0]=0
        i=0
        while i<len(arr):
            left=max(0,i-ranges[i])
            right=min(len(arr)-1,i+ranges[i])
            j=left+1
            while j<=right:
                arr[j]=min(arr[j],1+arr[left])
                j+=1
            i+=1
        if arr[-1]==float('inf'):
            return -1
        return arr[-1]


class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        dp = [n for _ in range(n+1)]
        for index,ranged in enumerate(ranges):
            start = max(0,index - ranged)
            end = min(n,index + ranged)
            if start == 0:
                extra = 0
            else:
                extra = dp[start]
            for i in range(start+1,end+1):
                dp[i]= min(dp[i],1 + extra) 
        if dp[-1]!=n:
            return dp[-1]
        else:
            return -1
        


class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        intervals=[]
        for i,r in enumerate(ranges):
            intervals.append([i-r,i+r])
        intervals.sort(key=lambda x:[x[0],-x[1]])
        #print(intervals)
        count=0
        def getnext(l):
            rel=[]
            for i in intervals:
                if l>=i[0] and l<i[1]:
                    rel.append(i)
            rel.sort(key=lambda x:x[1],reverse=True)
            return rel[0] if rel else None
        
        j=0
        while j<n:
            iv=getnext(j)
            #print(count,j,iv)
            if iv:
                j=iv[1]
                count+=1
            else:
                return -1
        return count

class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        intervals = []
        for i, x in enumerate(ranges):
            intervals.append([i - x, i + x])

        # Always pick the first
        def mySortKey(x):
            # print(x)
            left = x[0] 
            if left <= 0:
                left = 0
            right = x[1]
            
            return left * 100 - right
        
        intervals.sort(key=mySortKey)
        print(intervals)
        
        greedyFurthest = intervals[0][1]
        nextGreedyFurthest = 0
        j = 0
        count = 1
        
        while j < len(intervals):
            connect = False
            if greedyFurthest >= n:
                return count
            while j < len(intervals) and intervals[j][0] <= greedyFurthest:
                if intervals[j][1] > nextGreedyFurthest:
                    nextGreedyFurthest = intervals[j][1]
                j += 1
                connect = True
                
            greedyFurthest = nextGreedyFurthest
            count += 1
            if not connect:
                return -1
            
        if greedyFurthest >= n:
            return count
        else:
            return -1
            
        


class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        coords = []
        for i, rng in enumerate(ranges):
            if not rng:
                continue
            coords.append([max(0, i - rng), min(i + rng, n)])
        coords.sort()

        dp = [float('inf')] * (n + 1)
        dp[0] = 0
        
        for [start, end] in coords:
            if start > n:
                break
            prev = dp[start]
            for i in range(start, min(end, n)):
                dp[i + 1] = min(prev + 1, dp[i + 1])
            

        return  dp[-1] if dp[-1] < float('inf') else -1


class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        dp = [float('inf')]*(n+1)
        dp[0] = 0
        for i in range(n+1):
            L = max(0,i-ranges[i])
            R = min(n,i+ranges[i])
            
            for j in range(L+1,R+1):
                dp[j] = min(dp[j], dp[L]+1)
        if dp[n]>=n+2:
            return -1
        return dp[-1]

class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        areas = [(x - ranges[x], x + ranges[x]) for x in range(n+1)]
        areas = sorted(areas, key= lambda x: x[0])

        def get_intersections(current, intervals):
            results = []
            for interval in intervals:
                if current[0] <= interval[0] <= current[1] and interval[1] > current[1]:
                    results.append(interval)
            return results

        first = areas[0]
        for intersection in areas:
            if intersection[0] <= 0 and intersection[1] > first[1]:
                first = intersection

        selected = [first]
        area_to_cover = (first[1], n)

        while area_to_cover[0] < area_to_cover[1]:
            prev = selected[-1]

            intersections = get_intersections(prev, areas)
            if len(intersections) is 0:
                return -1

            intersections = sorted(intersections, key=lambda x: x[1])

            rightmost = intersections[-1]
            if rightmost[1] < area_to_cover[0]:
                return -1

            selected.append(rightmost)
            area_to_cover = (rightmost[1], n)

        return len(selected)

class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        dp = [n+2]*(n+1)
        dp[0] = 0
        for i in range(n+1):
            start = max(0,i-ranges[i])
            end = min(n,i+ranges[i])
            for j in range(start,end+1):
                dp[j] = min(dp[j],dp[start]+1)
        if dp[n]==n+2:
            return -1
        return dp[n]