from typing import List


class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        # find intervals starting from different locations
        intervals = []
        for center, width in enumerate(ranges):
            # if the element is 0, then this element is useless
            if width != 0:
                # restrict the interval in [0, n]
                interval = [max(0, center - width), min(center + width, n)]
                intervals.append(interval)
        # if every element is 0, then return -1
        if not intervals:
            return -1
        # find the furthest location it can reach from a current location
        d = {}
        for interval in intervals:
            if interval[0] not in d:
                d[interval[0]] = []
            d[interval[0]].append(interval[1])
        for k in d:
            d[k] = max(d[k])
        # current location
        loc = 0
        # result
        res = 0
        # if it doesn't reach the furthest location (n)
        while loc != n:
            # find the furthest location (max(...)) it can reach (<= d[k]) from our position (k)
            maxLocation = -1
            s = set()
            for k in d:
                if k <= loc:
                    s.add(k)
                    maxLocation = max(maxLocation, d[k])
            if maxLocation == -1:
                return -1
            # delete every element we iterate previously (we won't search elements again)
            for k in s:
                del d[k]
            res += 1
            loc = maxLocation
        return res