Given an array of integers arr and an integer d. In one step you can jump from index i to index:

i + x where: i + x < arr.length and  0 < x <= d.
i - x where: i - x >= 0 and  0 < x <= d.

In addition, you can only jump from index i to index j if arr[i] > arr[j] and arr[i] > arr[k] for all indices k between i and j (More formally min(i, j) < k < max(i, j)).
You can choose any index of the array and start jumping. Return the maximum number of indices you can visit.
Notice that you can not jump outside of the array at any time.
 
Example 1:

Input: arr = [6,4,14,6,8,13,9,7,10,6,12], d = 2
Output: 4
Explanation: You can start at index 10. You can jump 10 --> 8 --> 6 --> 7 as shown.
Note that if you start at index 6 you can only jump to index 7. You cannot jump to index 5 because 13 > 9. You cannot jump to index 4 because index 5 is between index 4 and 6 and 13 > 9.
Similarly You cannot jump from index 3 to index 2 or index 1.

Example 2:
Input: arr = [3,3,3,3,3], d = 3
Output: 1
Explanation: You can start at any index. You always cannot jump to any index.

Example 3:
Input: arr = [7,6,5,4,3,2,1], d = 1
Output: 7
Explanation: Start at index 0. You can visit all the indicies. 

Example 4:
Input: arr = [7,1,7,1,7,1], d = 2
Output: 2

Example 5:
Input: arr = [66], d = 1
Output: 1

 
Constraints:

1 <= arr.length <= 1000
1 <= arr[i] <= 10^5
1 <= d <= arr.length

Difficulty: interview

Starter code:

class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        

Solutions:
class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        dp = [1] * (len(arr) + 1)
        stack = []
        for i, n in enumerate(arr + [1000000]):
            while stack and arr[stack[-1]] < n:
                same_height_idx = [stack.pop()]
                while stack and arr[stack[-1]] == arr[same_height_idx[0]]:
                    same_height_idx.append(stack.pop())
                for j in same_height_idx:
                    # jump to left
                    if i - j <= d:
                        dp[i] = max(dp[i], dp[j] + 1)
                    # jump to right
                    if stack and j - stack[-1] <= d:
                        dp[stack[-1]] = max(dp[stack[-1]], dp[j] + 1)
            stack.append(i)
        return max(dp[:-1])

class Solution:
    def maxJumps(self, nums: List[int], d: int) -> int:
        # to_delete_index = set()
        # for i in range(1, len(arr)):
        #     if arr[i] == arr[i - 1]:
        #         to_delete_index.add(i)
        # nums = []
        # for i in range(0, len(arr)):
        #     if i not in to_delete_index:
        #         nums.append(arr[i])
        nums.append(math.inf) # 让所有元素都出栈
        dp = [1] * len(nums)
        stack = [] # 单调递减栈
        for i, cur in enumerate(nums):
            while stack and nums[stack[-1]] < cur:
                poped_same_val = [stack.pop()]
                while stack and nums[stack[-1]] == nums[poped_same_val[0]]:
                    poped_same_val.append(stack.pop())
                for poped in poped_same_val:
                    if i - poped <= d: # i是poped的右侧第一个相等或更大的元素
                        dp[i] = max(dp[i], dp[poped] + 1)
                    if stack and poped - stack[-1] <= d: # stack[-1]是poped的左侧第一个更大的元素
                        left_first_big_of_poped = stack[-1]
                        dp[left_first_big_of_poped] = max(dp[left_first_big_of_poped], dp[poped] + 1)
            stack.append(i)
            # print(i, dp, stack)
        return max(dp[:-1]) # 去掉最后一个inf在的位置的dp值

class Solution: # top-down dp
    # Time complexity O(ND)
    # Space complexity O(N) for dp
    def maxJumps(self, arr: List[int], d: int) -> int:
        n = len(arr)
        dp = [1] * (n+1)
        stack = []
        
        for i, a in enumerate(arr + [float('inf')]):
            while stack and arr[stack[-1]] < a:
                L = [stack.pop()]
                while stack and arr[stack[-1]] == arr[L[0]]:
                    L.append(stack.pop())
                for j in L:
                    if i - j<=d:
                        dp[i] = max(dp[i], dp[j] + 1)
                    if stack and j - stack[-1] <=d:
                        dp[stack[-1]] = max(dp[stack[-1]], dp[j] + 1)
            stack.append(i)
        return max(dp[:-1])    

class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        res = 0
        visited = {}
        
        def dfs(i):
            if i in visited:
                return visited[i]
            
            step = 1
            
            i_right = i + 1
            while i_right < len(arr) and i_right - i <= d:
                if arr[i_right] >= arr[i]:
                    break
                step = max(step, 1+dfs(i_right))
                i_right += 1
            
            i_left = i - 1
            while i_left >= 0 and i - i_left <= d:
                if arr[i_left] >= arr[i]:
                    break
                step = max(step, 1+dfs(i_left))
                i_left -= 1
            visited[i] = step
            return step
        
        
        for i in range(len(arr)):
            res = max(res, dfs(i))
        
        return res


class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        # @lru_cache(None)
        cache = {}
        def f(i):
            if i in cache:
                return cache[i]
            left = True
            right = True
            ret = 1
            for step in range(1,d+1):
                m = i - step
                if 0 <= m < len(arr) and arr[m] < arr[i] and left:
                    ret = max(ret,f(m)+1)
                else:
                    left = False
                m = i + step
                if 0 <= m < len(arr) and arr[m] < arr[i] and right:
                    ret = max(ret,f(m)+1)
                else:
                    right = False
                
                if (not left) and (not right):
                    break
            cache[i] = ret
            return ret
       
        mm = 0
        for i in range(len(arr)):
            fi = f(i) if i not in cache else cache[i]
            mm = max(f(i),mm)
        
        return mm




class Solution:
    # O(n x d) time, O(n) space
    def maxJumps(self, arr: List[int], d: int) -> int:
        n = len(arr)
        cache = {}
        def find_max_jumps(i):
            if i in cache:
                return cache[i]
            
            max_jumps = 1
            for dr in [1, -1]:
                for r in range(1, d + 1):
                    if not (0 <= i + dr * r < n and arr[i + dr * r] < arr[i]):
                        break
                    max_jumps = max(max_jumps, 1 + find_max_jumps(i + dr * r))
            
            cache[i] = max_jumps
            return max_jumps
        
        result = 1
        for i in range(n):
            result = max(result, find_max_jumps(i))
        return result


class Solution111:
    
    def maxJumps(self, arr: List[int], d: int) -> int:
        
        n = len(arr)
        res = [0] * n
        
        def dp(i):
            if res[i]: return res[i]
            res[i] = 1
            for di in [-1, 1]:
                for j in range(i+di, i+di+d*di, di):
                    if not (0 <= j < n and arr[j] < arr[i]):
                        break 
                    res[i] = max(res[i], dp(j)+1)
            return res[i]
        
        return max(map(dp, range(n)))

class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        @lru_cache(None)
        def dfs(index):
            res = 0
            
            for direction in [-1, 1]:
                for jump in range(1, d + 1):
                    j = index + direction*jump
                    if 0 <= j < len(arr) and arr[index] > arr[j]:
                        res = max(res, dfs(j))
                    else:
                        break
            
            return res + 1
        
        return max(dfs(i) for i in range(len(arr)))


from typing import List


class Solution:
  def maxJumps(self, arr: List[int], d: int) -> int:

    result = 0
    mapping = dict()
    for index, value in enumerate(arr):
      if index not in mapping:
        mapping[index] = set()
      for dd in range(1, d + 1):
        if index + dd >= len(arr):
          break

        if arr[index + dd] < arr[index]:
          mapping[index].add(index + dd)
        else:
          break

      for dd in range(1, d + 1):
        if index - dd < 0:
          break

        if arr[index - dd] < arr[index]:
          mapping[index].add(index - dd)
        else:
          break
      pass

    cache = dict()

    def dfs(cache, mapping, root):

      if root in cache:
        return cache[root]

      if root not in mapping:
        return 0

      result = 0
      for next in mapping[root]:
        result = max(result, dfs(cache, mapping, next) + 1)
        pass

      cache[root] = result
      return result

    result = 1
    for i in range(len(arr)):
      result = max(result, dfs(cache, mapping, i) + 1)

    return result


class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        n = len(arr)
        memo = [0] * n
        
        def dfs(start):
            if start < 0 or start >= n:
                return 0
            
            if memo[start] > 0:
                return memo[start]
            
            visited[start] = 1
            ret = 1
            for i in range(start-1, max(0, start - d) - 1, -1):
                if arr[i] >= arr[start]:
                    break
                if visited[i]:
                    continue
                ret = max(ret, dfs(i)+1)    
            for j in range(start+1, min(start + d, n-1) + 1):                
                if arr[j] >= arr[start]:
                    break
                if visited[j]:
                    continue
                ret = max(ret, dfs(j)+1)   
                
            visited[start] = 0
            memo[start] = ret
            return ret
        
        ret = 1
        visited = [0] * n
        for i in range(n):            
            ret = max(dfs(i), ret)   
        return ret

class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        def dfs(i):
            if i in cache:
                return cache[i]
            cache[i] = 1
            for neigh in g[i]:
                cache[i] = max(cache[i], 1 + dfs(neigh))
            return cache[i]
        
        g = defaultdict(set)
        for i in range(len(arr)):
            for x in range(1, d+1):
                if i-x >= 0 and arr[i-x] < arr[i]:
                    g[i].add(i-x)
                else:
                    break
            for x in range(1, d+1):
                if i+x < len(arr) and arr[i+x] < arr[i]:
                    g[i].add(i+x)
                else:
                    break
        cache = {}
        for i in range(len(arr)):
            dfs(i)
        return max(cache.values())
        '''
        mjump = 0
        for i, x in enumerate(arr):
            top = i
            bottom = i
            while top+1 < len(arr) and x>arr[top+1]:
                top += 1
            while bottom-1 >= 0 and x>arr[bottom-1]:
                bottom -=1
            newarr = arr[bottom:top+1]
            
            jump =[x]
            value = x-1
            while value>=min(newarr):
                if value < jump[-1]-d:
                    break
                elif value in newarr:
                    jump.append(value)
                value -= 1
            
            print(jump)
            mjump = max(mjump, len(jump))
        
        return mjump
        '''
                
            
            


class Solution:
    def helper(self, idx):
        if self.dp[idx] != float('inf'):
            return self.dp[idx]

        max_step = 1
        # to left
        for c in range(idx - 1, max(0, idx - self.d) - 1, -1):
            if self.arr[idx] <= self.arr[c]:
                break

            max_step = max(self.helper(c) + 1, max_step)

        # to right
        for c in range(idx + 1, min(self.n, idx + self.d + 1)):
            if self.arr[idx] <= self.arr[c]:
                break

            max_step = max(self.helper(c) + 1, max_step)

        self.dp[idx] = max_step
        return max_step

    def maxJumps(self, arr: List[int], d: int) -> int:
        self.n = len(arr)
        self.d = d
        self.arr = arr
        self.dp = [float('inf')] * self.n

        self.trans = defaultdict(list)

        max_ = 0
        for i in range(self.n):
            max_ = max(self.helper(i), max_)

        return max_

class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        n = len(arr)
        memo = {}
        
        
        def dfs(start):
            if start < 0 or start >= n:
                return 0
            
            if start in memo:
                return memo[start]
            
            visited[start] = 1
            ret = 1
            for i in range(start-1, max(0, start - d) - 1, -1):
                if arr[i] >= arr[start]:
                    break
                if visited[i]:
                    continue
                ret = max(ret, dfs(i)+1)    
            for j in range(start+1, min(start + d, n-1) + 1):                
                if arr[j] >= arr[start]:
                    break
                if visited[j]:
                    continue
                ret = max(ret, dfs(j)+1)   
                
            visited[start] = 0
            memo[start] = ret
            return ret
        
        ret = 1
        visited = [0] * n
        for i in range(n):            
            ret = max(dfs(i), ret)   
        return ret

class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        n = len(arr)
        memo = {}
        
        def dfs(start):
            if start < 0 or start >= n:
                return 0
            
            if start in memo:
                return memo[start]
            
            visited[start] = 1
            ret = 1
            for i in range(start-1, max(0, start - d) - 1, -1):
                if arr[i] >= arr[start]:
                    break
                if visited[i]:
                    continue
                ret = max(ret, dfs(i)+1)    
            for j in range(start+1, min(start + d, n-1) + 1):                
                if arr[j] >= arr[start]:
                    break
                if visited[j]:
                    continue
                ret = max(ret, dfs(j)+1)   
                
            visited[start] = 0
            memo[start] = ret
            return ret
        
        ret = 1
        visited = [0] * n
        for i in range(n):            
            ret = max(dfs(i), ret)   
        return ret

class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        n = len(arr)
        
        graph = collections.defaultdict(list)
        
        st = []
        for i in range(n):
            while st and arr[st[-1]] < arr[i]:
                j = st.pop()
                if i - j <= d:
                    graph[j].append(i)
            st.append(i)
        
        st = []
        for i in range(n-1, -1, -1):
            while st and arr[st[-1]] < arr[i]:
                j = st.pop()
                if j - i <= d:
                    graph[j].append(i)
            st.append(i)
        
        visited = {}
        def dfs(i):
            if i in visited:
                return visited[i]
            step = 1
            for j in graph[i]:
                step = max(step, 1+dfs(j))
            visited[i] = step
            return step
        
        res = 0
        for i in range(n):
            res = max(res, dfs(i))
                
        return res


class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        
        def helper(arr,index,d,memo):
            if arr[index] < 0 or not (0 <= index < len(arr)):
                return 0
            if index in memo:
                return memo[index]
            left_visited = 0
            right_visited = 0
            arr[index] = -arr[index]
            for i in range(index+1,index+d+1):
                # if p:
                #     pass
                #     # print(f'{index}, {i}')
                if i >= len(arr):
                    break
                if abs(arr[i]) >= abs(arr[index]):
                    break
                if arr[i] < 0:
                    continue
                # if p:
                #     print(f'using index-{index},{i}')
                left_visited = max(left_visited,helper(arr,i,d,memo))
            
            for j in range(index-1,index-d-1,-1):
                # if p:
                #     pass
                    # print(f'{index}, {j}')
                if j < 0:
                    break
                if abs(arr[j]) >= abs(arr[index]):
                    break
                if arr[j] < 0:
                    continue
                right_visited = max(right_visited,helper(arr,j,d,memo))
            arr[index] = -arr[index]
            # if p:
            #     # pass
            #     print(f'{index}--{left_visited},{right_visited}')
            memo[index] = 1 + max(left_visited,right_visited)
            return memo[index]
        
        
        max_visited = 1
        p = False
        memo = {}
        for index in range(len(arr)):
            # if index == 2:
                # p = True
            visited = helper(arr,index,d,memo)
            # print(f'from {index} max is {visited}')
            max_visited = max(visited,max_visited)
        
        return max_visited


class Solution:
    from collections import deque
    def maxJumps(self, arr: List[int], d: int) -> int:
        q=deque()
        n=len(arr)
        dp=[-1]*n
        
        def solve(node):
            if node<0 or node>=n:
                return -1
            
            if dp[node]!=-1:
                return dp[node]
            
            ans=0
            for i in range(1,d+1):
                if node+i>=n or arr[node+i]>=arr[node]:
                    break
                #print(node,i+node)
                ans=max(ans,solve(i+node))
            
            for i in range(1,d+1):
                if node-i<0 or arr[node-i]>=arr[node]:
                    break
                #print(node,-i+node)
                ans=max(ans,solve(node-i))
            
            dp[node]=1+ans
            
            return dp[node]
        
        for i in range(n):
            solve(i)
        
        #print(dp)
        return max(dp)


class Solution:
    def maxJumps(self, lst: List[int], d: int) -> int:
        
        
        
        def Ab(i,d,X):
            if i<0 or i>= len(lst):
                return -1
            
            if X<=lst[i]:
                return None
            
            if dp[i] != -1:
                return dp[i]
            m = 1
            for j in range(1,d+1):
                a = 0
                a = Ab(i-j,d,lst[i])
                if a == None:
                    break                
                m = max(m,1+a)
                              
            for j in range(1,d+1):
                b = 0
                b = Ab(i+j,d,lst[i])
                if b == None:
                    break                
                m = max(m,1+b)
            dp[i] = m
            return dp[i]
        dp = [-1 for i in lst]
        for i in range(len(lst)-1,-1,-1):
            Ab(i,d,sys.maxsize)
        return max(dp)

class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        ans = [1] * len(arr)
        
        def dp(i):
            nonlocal ans, arr, d
            if ans[i] != 1:
                return ans[i]
            for dr in [-1, 1]:
                for k in range(i, i + d * dr + dr, dr):
                    if k < 0 or k == i:
                        continue
                    if k > len(arr) - 1 or arr[k] >= arr[i]:
                        break
                    ans[i] = max(ans[i], 1 + dp(k))
            return ans[i]
        
        for i in range(len(arr)):
            dp(i)
        return max(ans)
                


class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        mem = [0] * len(arr)
        
        def dfs(i):
            if mem[i]:
                return mem[i]
            num = 1
            
            j = i+1
            while j in range(i+1, min(len(arr), i+d+1)) and arr[j] < arr[i]:
                num = max(num, dfs(j) + 1)
                j += 1
            
            j = i-1
            while j in range(max(0, i-d), i) and arr[j] < arr[i]:
                num = max(num, dfs(j) + 1)
                j -= 1
                
            mem[i] = num   
            return mem[i]
        
        res = 0
        for i in range(len(arr)):
            dfs(i)
            res = max(res, dfs(i) + 1)
            
        return max(mem)

import collections

class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        
        outEdges = {}
        inEdges = {}
        
        for idx, height in enumerate(arr):
            
            jumpRangeRight = list(range(idx+1, min(len(arr), idx+d+1)))
            jumpRangeLeft = list(range(idx-1, max(0, idx - d) - 1, -1))
            
            for jumpRange in [jumpRangeLeft, jumpRangeRight]:
                for jumpIdx in jumpRange:
                    if arr[jumpIdx] >= arr[idx]:
                        break

                    if idx not in outEdges:
                        outEdges[idx] = set()
                    outEdges[idx].add(jumpIdx)

                    if jumpIdx not in inEdges:
                        inEdges[jumpIdx] = set()
                    inEdges[jumpIdx].add(idx)
        
        noInEdges = collections.deque()
        for idx in range(len(arr)):
            if idx not in inEdges:
                noInEdges.append(idx)
        
        topologicalOrder = collections.deque()
        while noInEdges:
            idx = noInEdges.pop()
            topologicalOrder.append(idx)
            if idx not in outEdges:
                continue
            for jumpIdx in outEdges[idx]:
                inEdges[jumpIdx].remove(idx)
                if not inEdges[jumpIdx]:
                    noInEdges.append(jumpIdx)
        
        maxJumps = 1
        jumpCount = [1] * len(arr)
        for idx in topologicalOrder:
            
            if idx not in outEdges:
                continue
            
            for jumpIdx in outEdges[idx]:
                jumpCount[jumpIdx] = max(jumpCount[idx] + 1, jumpCount[jumpIdx])
                maxJumps = max(jumpCount[jumpIdx], maxJumps)
                
        return maxJumps
        
    def maxJumpsBfs(self, arr: List[int], d: int) -> int:
        bfs = collections.deque()
        
        for idx in range(len(arr)):
            bfs.append((idx, 1))
        
        stepCount = {}
        maxSteps = 0
        
        while bfs:
            idx, steps = bfs.popleft()

            # Already found more steps to this index.
            if idx in stepCount and steps <= stepCount[idx]:
                continue 
            stepCount[idx] = steps

            maxSteps = max(steps, maxSteps)

            # Process jumps to the right
            for jumpIdx in range(idx+1, min(len(arr), idx+d+1)):
                # Can't jump past taller buildings, break loop
                if arr[jumpIdx] >= arr[idx]:
                    break
                    
                # Explore this jump
                bfs.append((jumpIdx, steps+1))

            # Process jumps to the left
            for jumpIdx in range(idx-1, max(0, idx-d) -1, -1):
                # Can't jump past taller buildings, break loop
                if arr[jumpIdx] >= arr[idx]:
                    break

                # Search the next step
                bfs.append((jumpIdx, steps+1))
            
        return maxSteps
                


import collections

class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        
        outEdges = {}
        inEdges = {}
        
        for idx, height in enumerate(arr):
            
            jumpRangeRight = list(range(idx+1, min(len(arr), idx+d+1)))
            jumpRangeLeft = list(range(idx-1, max(0, idx - d) - 1, -1))
            
            for jumpRange in [jumpRangeLeft, jumpRangeRight]:
                for jumpIdx in jumpRange:
                    if arr[jumpIdx] >= arr[idx]:
                        break

                    if idx not in outEdges:
                        outEdges[idx] = set()
                    outEdges[idx].add(jumpIdx)

                    if jumpIdx not in inEdges:
                        inEdges[jumpIdx] = set()
                    inEdges[jumpIdx].add(idx)
        
        noInEdges = collections.deque()
        for idx in range(len(arr)):
            if idx not in inEdges:
                noInEdges.append(idx)
        
        topologicalOrder = []
        while noInEdges:
            idx = noInEdges.pop()
            topologicalOrder.append(idx)
            if idx not in outEdges:
                continue
            for jumpIdx in outEdges[idx]:
                inEdges[jumpIdx].remove(idx)
                if not inEdges[jumpIdx]:
                    noInEdges.append(jumpIdx)
        
        maxJumps = 1
        jumpCount = [1] * len(arr)
        for idx in topologicalOrder:
            
            if idx not in outEdges:
                continue
            
            for jumpIdx in outEdges[idx]:
                jumpCount[jumpIdx] = max(jumpCount[idx] + 1, jumpCount[jumpIdx])
                maxJumps = max(jumpCount[jumpIdx], maxJumps)
                
        return maxJumps
        
    def maxJumpsBfs(self, arr: List[int], d: int) -> int:
        bfs = collections.deque()
        
        for idx in range(len(arr)):
            bfs.append((idx, 1))
        
        stepCount = {}
        maxSteps = 0
        
        while bfs:
            idx, steps = bfs.popleft()

            # Already found more steps to this index.
            if idx in stepCount and steps <= stepCount[idx]:
                continue 
            stepCount[idx] = steps

            maxSteps = max(steps, maxSteps)

            # Process jumps to the right
            for jumpIdx in range(idx+1, min(len(arr), idx+d+1)):
                # Can't jump past taller buildings, break loop
                if arr[jumpIdx] >= arr[idx]:
                    break
                    
                # Explore this jump
                bfs.append((jumpIdx, steps+1))

            # Process jumps to the left
            for jumpIdx in range(idx-1, max(0, idx-d) -1, -1):
                # Can't jump past taller buildings, break loop
                if arr[jumpIdx] >= arr[idx]:
                    break

                # Search the next step
                bfs.append((jumpIdx, steps+1))
            
        return maxSteps
                


class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        result = 1
        N = len(arr)
        cache = {}
        def helper(i : int) -> int:
            if i in cache:
                return cache[i]
            result = 1
            if ((i == 0 or arr[i] <= arr[i - 1]) and
                (i == N - 1 or arr[i] <= arr[i + 1])):
                cache[i] = result
                return cache[i]
            j = i - 1
            while j >= 0 and j >= i - d and arr[j] < arr[i]:
                cur = helper(j)
                result = max(result, cur + 1)
                j = j - 1
            j = i + 1
            while j < N and j <= i + d and arr[j] < arr[i]:
                cur = helper(j)
                result = max(result, cur + 1)
                j = j + 1
            cache[i] = result
            return cache[i]
        
        for i in range(N):
            cur = helper(i)
            result = max(cur, result)
        return result

import collections

class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        
        outEdges = {}
        inEdges = {}
        
        for idx, height in enumerate(arr):
            
            jumpRangeRight = list(range(idx+1, min(len(arr), idx+d+1)))
            jumpRangeLeft = list(range(idx-1, max(0, idx - d) - 1, -1))
            
            for jumpRange in [jumpRangeLeft, jumpRangeRight]:
                for jumpIdx in jumpRange:
                    if arr[jumpIdx] >= arr[idx]:
                        break

                    if idx not in outEdges:
                        outEdges[idx] = set()
                    outEdges[idx].add(jumpIdx)

                    if jumpIdx not in inEdges:
                        inEdges[jumpIdx] = set()
                    inEdges[jumpIdx].add(idx)
        
        noInEdges = collections.deque()
        for idx in range(len(arr)):
            if idx not in inEdges:
                noInEdges.append(idx)
        
        topologicalOrder = collections.deque()
        while noInEdges:
            idx = noInEdges.pop()
            topologicalOrder.append(idx)
            if idx not in outEdges:
                continue
            for jumpIdx in outEdges[idx]:
                inEdges[jumpIdx].remove(idx)
                if not inEdges[jumpIdx]:
                    noInEdges.append(jumpIdx)
        
        maxJumps = 1
        jumpCount = [1] * len(arr)
        while topologicalOrder:
            idx = topologicalOrder.popleft()
            
            if idx not in outEdges:
                continue
            
            for jumpIdx in outEdges[idx]:
                jumpCount[jumpIdx] = max(jumpCount[idx] + 1, jumpCount[jumpIdx])
                maxJumps = max(jumpCount[jumpIdx], maxJumps)
                
        return maxJumps
        
    def maxJumpsBfs(self, arr: List[int], d: int) -> int:
        bfs = collections.deque()
        
        for idx in range(len(arr)):
            bfs.append((idx, 1))
        
        stepCount = {}
        maxSteps = 0
        
        while bfs:
            idx, steps = bfs.popleft()

            # Already found more steps to this index.
            if idx in stepCount and steps <= stepCount[idx]:
                continue 
            stepCount[idx] = steps

            maxSteps = max(steps, maxSteps)

            # Process jumps to the right
            for jumpIdx in range(idx+1, min(len(arr), idx+d+1)):
                # Can't jump past taller buildings, break loop
                if arr[jumpIdx] >= arr[idx]:
                    break
                    
                # Explore this jump
                bfs.append((jumpIdx, steps+1))

            # Process jumps to the left
            for jumpIdx in range(idx-1, max(0, idx-d) -1, -1):
                # Can't jump past taller buildings, break loop
                if arr[jumpIdx] >= arr[idx]:
                    break

                # Search the next step
                bfs.append((jumpIdx, steps+1))
            
        return maxSteps
                


class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        def find_longest_l(pos, d):
            if pos - 1 < 0 or arr[pos-1] > arr[pos]:
                return pos
            i = pos
            while i > 0 and abs(pos - i) < d and arr[i-1] < arr[pos]:
                i -= 1
            return i
        
        def find_longest_r(pos, d):
            if pos + 1 >= len(arr) or arr[pos+1] > arr[pos]:
                return pos
            i = pos
            while i < len(arr) - 1 and abs(pos - i) < d and arr[i+1] < arr[pos]:
                i += 1
            return i
        
        def jump(pos, number_of_locations, seen):
            maximum_locations = number_of_locations
            L = find_longest_l(pos, d)
            R = find_longest_r(pos, d)
                        
            for i in range(L, R+1):
                if i == pos:
                    continue  
                if i not in seen: 
                    jumps_to_i = jump(i, number_of_locations, seen)
                    maximum_locations = max(maximum_locations, jumps_to_i + 1) 
                else:
                    jumps_to_i = seen[i]
                    maximum_locations = max(maximum_locations, jumps_to_i + 1) 

            seen[pos] = maximum_locations
            return maximum_locations
      
        indices = [(i, arr[i]) for i in range(len(arr))]
        indices.sort(key=lambda x: x[1], reverse=True)
        
        seen = {}
        return max(jump(x[0], 1, seen) for x in indices)
            


class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        def find_longest_l(pos, d):
            if pos - 1 < 0 or arr[pos-1] > arr[pos]:
                return pos
            i = pos
            while i > 0 and abs(pos - i) < d and arr[i-1] < arr[pos]:
                i -= 1
            return i
        
        def find_longest_r(pos, d):
            if pos + 1 >= len(arr) or arr[pos+1] > arr[pos]:
                return pos
            i = pos
            while i < len(arr) - 1 and abs(pos - i) < d and arr[i+1] < arr[pos]:
                i += 1
            return i
        
        def jump(pos, number_of_locations, seen):
            maximum_locations = number_of_locations
            # print(\"currently at:\", arr[pos], \"maximum location:\", number_of_locations)            
            L = find_longest_l(pos, d)
            R = find_longest_r(pos, d)
                        
            for i in range(L, R+1):
                if i == pos:
                    continue  
                if i not in seen: 
                    jumps_to_i = jump(i, number_of_locations, seen)
                    maximum_locations = max(maximum_locations, jumps_to_i + 1) 
                else:
                    # print(\"seen:\", i, seen[i])
                    jumps_to_i = seen[i]
                    maximum_locations = max(maximum_locations, jumps_to_i + 1) 
                # print(\"pos:\", pos, \"max visits:\", maximum_locations)

            # print(\"Backtracking\")
            seen[pos] = maximum_locations
            # print(\"pos:\", arr[pos], \"seen:\", seen)
            return maximum_locations
      
        indices = [(i, arr[i]) for i in range(len(arr))]
        indices.sort(key=lambda x: x[1], reverse=True)
        
        seen = {}
        # print(seen)
        return max(jump(x[0], 1, seen) for x in indices)
            


class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        def find_longest_l(pos, d):
            if pos - 1 < 0 or arr[pos-1] > arr[pos]:
                return pos
            i = pos
            while i > 0 and abs(pos - i) < d and arr[i-1] < arr[pos]:
                i -= 1
            return i
        
        def find_longest_r(pos, d):
            if pos + 1 >= len(arr) or arr[pos+1] > arr[pos]:
                return pos
            i = pos
            while i < len(arr) - 1 and abs(pos - i) < d and arr[i+1] < arr[pos]:
                i += 1
            return i
        
        def jump(pos, number_of_locations, seen):
            maximum_locations = number_of_locations
            L = find_longest_l(pos, d)
            R = find_longest_r(pos, d)
                        
            for i in range(L, R+1):
                if i == pos:
                    continue  
                if i not in seen: 
                    jumps_to_i = jump(i, number_of_locations, seen)
                    maximum_locations = max(maximum_locations, jumps_to_i + 1) 
                else:
                    jumps_to_i = seen[i]
                    maximum_locations = max(maximum_locations, jumps_to_i + 1) 

            # print(\"Backtracking\")
            seen[pos] = maximum_locations
            # print(\"pos:\", arr[pos], \"seen:\", seen)
            return maximum_locations
      
        indices = [(i, arr[i]) for i in range(len(arr))]
        indices.sort(key=lambda x: x[1], reverse=True)
        
        seen = {}
        # print(seen)
        return max(jump(x[0], 1, seen) for x in indices)
            


class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        l = len(arr)
        self.check, self.seen = [[] for _ in range(l)], dict()
        for i, v in enumerate(arr):
            for sign in (1, -1):
                for x in range(sign, (d + 1) * sign, sign):
                    if i + x not in list(range(l)) or v <= arr[i + x]:
                        break
                    self.check[i].append(i + x)
            if not self.check[i]:
                self.seen[i] = 1
        return max(self.helper(i) for i in range(l))
        
    def helper(self, p):
        if p not in self.seen:
            res = 0
            for n in self.check[p]:
                res = max(res, self.seen.get(n, self.helper(n)) + 1)
            self.seen[p] = res
        return self.seen[p]


class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        ans = [1] * len(arr)
        
        def dp(i):
            if ans[i] != 1:
                return ans[i]
            for dr in [-1, 1]:
                for k in range(i, i + d * dr + dr, dr):
                    if k == i:
                        continue
                    if not (0 <= k < len(arr) and arr[k] < arr[i]):
                        break
                    ans[i] = max(ans[i], 1 + dp(k))
            return ans[i]
        
        for i in range(len(arr)):
            dp(i)
        return max(ans)
                


class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        n = len(arr)
        memo = {}
        
        
        def dfs(start, visited):
            if start < 0 or start >= n:
                return 0
            
            if start in memo:
                return memo[start]
            
            visited[start] = 1
            ret = 1
            for i in range(start-1, max(0, start - d) - 1, -1):
                if arr[i] >= arr[start]:
                    break
                if visited[i]:
                    continue
                ret = max(ret, dfs(i, visited)+1)    
            for j in range(start+1, min(start + d, n-1) + 1):                
                if arr[j] >= arr[start]:
                    break
                if visited[j]:
                    continue
                ret = max(ret, dfs(j, visited)+1)   
                
            visited[start] = 0
            memo[start] = ret
            return ret
        
        ret = 1
        for i in range(n):
            visited = [0] * n
            ret = max(dfs(i, visited), ret)
            #print(i,ret, memo)
        
        return ret

class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        '''
        [6,4,14,6,8,13,9,7,10,6,12], d = 2
        dp(i) = 1 + 
        max{
        within i-d <j< i+d
        not arr[k] > arr[i] between i, j
        }
        res = 0
        j from i-1 to i-d (0<=j<len(arr)), while arr[j]<arr[i]: res = max(res, recurse j) 
        i+1 to i+d
        memo
        return res + 1
        
        '''
        max_pos = 1
        memo = {}
        def helper(i):
            if i in list(memo.keys()): return memo[i]
            res = 0
            j = i-1
            while 0<=j<len(arr) and i-j<=d and arr[j]<arr[i]:
                res = max(res, helper(j))
                j -= 1
            j = i+1
            while 0<=j<len(arr) and j-i<=d and arr[j]<arr[i]:
                res = max(res, helper(j))
                j += 1
            res = res + 1
            memo[i] = res
            return res
        
        for i in range(len(arr)):
            max_pos = max(max_pos, helper(i))
        # print(memo)
        return max_pos
            


class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        def backtracking(idx):
            nonlocal memo, max_val
            if idx in memo: return memo[idx]
            lstack = []
            rstack = []
            lbarrier = False
            rbarrier = False
            for i in range(1, d + 1):
                if not lbarrier and idx - i >= 0 and arr[idx - i] < arr[idx]:
                    lstack.append(idx - i)
                else:
                    lbarrier = True
                if not rbarrier and idx + i < len(arr) and arr[idx + i] < arr[idx]:
                    rstack.append(idx + i)
                else:
                    rbarrier = True
            # if idx == 10: print(lstack, rstack)
            ljump = 1
            while lstack:
                lidx = lstack.pop()
                ljump = max(ljump, 1 + backtracking(lidx))
            rjump = 1
            while rstack:
                ridx = rstack.pop()
                rjump = max(rjump, 1 + backtracking(ridx))
            jump = max(ljump, rjump)
            memo[idx] = jump
            max_val = max(max_val, jump)
            return jump
        memo = {}
        max_val = 0
        for i in range(len(arr)):
            backtracking(i)
            
        return max_val

class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        jumps = defaultdict(list)
        
        def check(it):
            stack = []
            for i in it:
                while stack and arr[stack[-1]] < arr[i]:
                    j = stack.pop()
                    if abs(i - j) <= d:
                        jumps[j].append(i)
                stack.append(i)
        N = len(arr)
        check(range(N))
        check(reversed(range(N)))
        
        @lru_cache(None)
        def dfs(i):
            return 1 + max((dfs(j) for j in jumps[i]), default = 0)
        
        return max((dfs(i) for i in range(N)))

class Solution:
    def maxJumps(self, A: List[int], d: int) -> int:
        dp = [1]*len(A)
        steps = [(v,i) for i,v in enumerate(A)]
        steps.sort()
        for val, i in steps:
            maxVal = val
            for j in range(i+1, min(i+d+1,len(steps))):
                if A[j] > maxVal:
                    maxVal = max(maxVal,A[j])
                    dp[j] = max(dp[j], dp[i]+1)
            maxVal = val 
            for j in reversed(range(max(i-d,0),i)):
                if A[j] > maxVal:
                    maxVal = max(maxVal,A[j])
                    dp[j] = max(dp[j], dp[i]+1)
        return max(dp)

class Solution:
    def maxJumps(self, A: List[int], d: int) -> int:
        # there is some topological order
        # but now it is asking for the longest path 
        # now we have to start at the root of the tree, and then maximize the 
        # distance of each node 
        # building the graph is tricky 
        # sliding window for building the graph 
        # i -> j if arr[i] > arr[j] but not the otherway around 
        # so we have to use a deque and pop out the indices greater than d away 
        
        '''
        6 4
        14 -> 6, (0), 14 -> 4 (1)
        14 -> (3), 
        14 -> (4), (4) -> (3)
        
        '''
        
        n = len(A)
        graph = {}
        inorder = [0]*n
        for i in range(n):
          graph[i] = []
          is_greater = False
          cur_max = -1
          for ind in range(i-1, max(-1, i-d-1), -1):
            if A[ind] >= A[i]:
              if A[ind] >= cur_max and A[ind] > A[i]:
                cur_max = A[ind]
                graph[ind].append(i)
                inorder[i] += 1
              is_greater = True
            else:
              if is_greater: continue
              graph[i].append(ind)
              inorder[ind] += 1
        stack = []
        dp = [1]*n
        for i in range(n):
          if inorder[i] == 0:
            stack.append(i)
        while stack:
          top = stack.pop()
          for value in graph[top]:
            inorder[value] -= 1
            dp[value] = max(dp[value], dp[top] + 1)
            if inorder[value] == 0:
              stack.append(value)
              
        # print(A[20:60])
        # print([(i, v)  for i,v in enumerate(dp)][:60])
        return max(dp)


class Solution:
    def maxJumps(self, A: List[int], d: int) -> int:
        # there is some topological order
        # but now it is asking for the longest path 
        # now we have to start at the root of the tree, and then maximize the 
        # distance of each node 
        # building the graph is tricky 
        # sliding window for building the graph 
        # i -> j if arr[i] > arr[j] but not the otherway around 
        # so we have to use a deque and pop out the indices greater than d away 
        
        '''
        6 4
        14 -> 6, (0), 14 -> 4 (1)
        14 -> (3), 
        14 -> (4), (4) -> (3)
        
        '''
        
        n = len(A)
        graph = {}
        inorder = [0]*n
        for i in range(n):
          graph[i] = []
          is_greater = False
          cur_max = -1
          for ind in range(i-1, max(-1, i-d-1), -1):
            if A[ind] > A[i]:
              if A[ind] >= cur_max:
                cur_max = A[ind]
                graph[ind].append(i)
                inorder[i] += 1
              is_greater = True
            else:
              if is_greater: continue
              if A[i] == A[ind]: break
              graph[i].append(ind)
              inorder[ind] += 1
        stack = []
        dp = [1]*n
        for i in range(n):
          if inorder[i] == 0:
            stack.append(i)
        while stack:
          top = stack.pop()
          for value in graph[top]:
            inorder[value] -= 1
            dp[value] = max(dp[value], dp[top] + 1)
            if inorder[value] == 0:
              stack.append(value)
              
        # print(A[20:60])
        # print([(i, v)  for i,v in enumerate(dp)][:60])
        print(dp)
        return max(dp)


class Solution:
    def maxJumps(self, A: List[int], d: int) -> int:
        dp = [1]*len(A)
        steps = [(v,i) for i,v in enumerate(A)]
        steps.sort()
        print(steps)
        for val, i in steps:
            maxVal = val
            for j in range(i+1, min(i+d+1,len(steps))):
                if A[j] > maxVal:
                    maxVal = max(maxVal,A[j])
                    dp[j] = max(dp[j], dp[i]+1)
            maxVal = val 
            for j in reversed(range(max(i-d,0),i)):
                if A[j] > maxVal:
                    maxVal = max(maxVal,A[j])
                    dp[j] = max(dp[j], dp[i]+1)
        print(dp)
        return max(dp)

class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        book = [1]*len(arr)
        index = collections.defaultdict(list)
        for i in range(len(arr)):
            index[arr[i]].append(i)
        val = list(index.keys())
        val.sort(reverse = True)
        for v in val:
            for i in index[v]:
                height = arr[i]
                for j in range(i+1, i+d+1):
                    if j == len(arr):
                        break
                    if arr[j] > height:
                        book[i] = max(book[i], book[j]+1)
                        height = arr[j]
                height = arr[i]
                for j in range(i-1, i-d-1, -1):
                    if j == -1:
                        break
                    if arr[j] > height:
                        book[i] = max(book[i], book[j]+1)
                        height = arr[j]
        return max(book)

class Solution: # top-down dp
    # Time complexity O(ND)
    # Space complexity O(N) for dp
    def maxJumps(self, arr: List[int], d: int) -> int:

        
        n, inf = len(arr), float('inf')
        a, s = [[] for _ in range(n)], [(inf, -1)]
        
        for i, x in enumerate(arr):
            while s[-1][0] < x:
                if s[-1][1] >= i-d:
                    a[i].append(s[-1][1])
                s.pop()
            s.append((x, i))
        
        s = [(inf, -1)]
        for i, x in reversed(list(enumerate(arr))):
            while s[-1][0] < x:
                if s[-1][1] <= i+d:
                    a[i].append(s[-1][1])
                s.pop()
            s.append((x, i))
        
        dp, v = [1]*n, [0]*n
        def dfs(i):
            if v[i]: return
            v[i] = 1
            for j in a[i]:
                dfs(j)
                dp[i] = max(dp[i], dp[j]+1)
        
        for i in range(n): dfs(i)
        return max(dp)


class Solution:
    def maxJumps(self, A: List[int], d: int) -> int:
        N = len(A)
        jumpable = collections.defaultdict(list)
        
        def find_jumpable_indices(iter):
            stack = []
            for i in iter:
                while stack and A[stack[-1]] < A[i]:
                    j = stack.pop()
                    if abs(i - j) <= d:
                        jumpable[i].append(j)
                stack.append(i)

        find_jumpable_indices(list(range(N)))
        find_jumpable_indices(reversed(list(range(N))))
        
        dp = [-1] * N
        def dfs(idx):
            if dp[idx] > -1:
                return dp[idx]
            res = 1
            for j in jumpable[idx]:
                res = max(res, 1 + dfs(j))
            
            dp[idx] = res
            return res
        
        return max(list(map(dfs, list(range(N)))))


class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        n = len(arr)
        dp = [1] * (n+1)
        stack = []
        for i, a in enumerate(arr + [float('inf')]):
            while stack and arr[stack[-1]] < a:
                last = [stack.pop()]
                while stack and arr[stack[-1]] == arr[last[0]]:
                    last.append(stack.pop())
                for j in last:
                    if i-j <= d:
                        dp[i] = max(dp[i], dp[j]+1)
                    if stack and j - stack[-1] <= d:
                        dp[stack[-1]] = max(dp[stack[-1]], dp[j]+1)
            stack.append(i)
        return max(dp[:-1])

class Solution:
    def maxJumps(self, arr, d):
        n = len(arr)
        dp = [1] * (n+1)
        stack = []
        
        for i, a in enumerate(arr + [float('inf')]):
            while stack and arr[stack[-1]] < a:
                L = [stack.pop()]
                while stack and arr[stack[-1]] == arr[L[0]]:
                    L.append(stack.pop())
                for j in L:
                    if i - j<=d:
                        dp[i] = max(dp[i], dp[j] + 1)
                    if stack and j - stack[-1] <=d:
                        dp[stack[-1]] = max(dp[stack[-1]], dp[j] + 1)
            stack.append(i)
        return max(dp[:-1])    

from collections import *
from functools import *
import numpy as np
from typing import *


class Solution:
    def maxJumps(self, nums: List[int], d: int) -> int:
        N = len(nums)
        left_jumps = [[] for _ in range(N)]
        left = [(-1, np.inf)]
        for i in range(N):
            while left[-1][1] < nums[i]:
                j, _ = left.pop()
                if abs(j - i) <= d:
                    left_jumps[i].append(j)
            left.append((i, nums[i]))
        
        right_jumps = [[] for _ in range(N)]
        right = [(-1, np.inf)]
        for i in reversed(range(N)):
            while right[-1][1] < nums[i]:
                j, _ = right.pop()
                if abs(j - i) <= d:
                    right_jumps[i].append(j)
            right.append((i, nums[i]))
        
        @lru_cache(maxsize=None)
        def longest_path_from(pos: int):
            left_max = max((longest_path_from(p) for p in left_jumps[pos]), default=0)
            right_max = max((longest_path_from(p) for p in right_jumps[pos]), default=0)
            return max(1 + left_max, 1 + right_max)

        return max(longest_path_from(i) for i in range(N))

class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        A = arr
        n = len(A)
        # comp = 0
        @lru_cache(None)
        def dp(i):
            # nonlocal comp
            # comp += 1
            count = 0
            for j in range(i-1, i-d-1, -1):
                if j >= 0 and A[j] < A[i]:
                    count = max(count, dp(j))
                else:
                    break
            for j in range(i+1, i+d+1):
                if j < n and A[j] < A[i]:
                    count = max(count, dp(j))
                else:
                    break
            return count + 1
        
        res = 0
        for k in range(n):
            res = max(res, dp(k))
        # print(comp)
        return res

class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        arr.append(math.inf) # 让所有元素都出栈
        dp = [1] * len(arr)
        stack = [] # 单调递减栈
        for i, cur in enumerate(arr):
            while stack and arr[stack[-1]] < cur:
                poped_same_val = [stack.pop()]
                while stack and arr[stack[-1]] == arr[poped_same_val[0]]: # val一样的元素，他们的right_first_bigger和left_first_bigger都是一样的，要一起拿出来更新。
                    poped_same_val.append(stack.pop())
                for poped in poped_same_val:
                    if i - poped <= d: # i是poped的右侧第一个相等或更大的元素
                        dp[i] = max(dp[i], dp[poped] + 1)
                    if stack and poped - stack[-1] <= d: # stack[-1]是poped的左侧第一个更大的元素
                        left_first_big_of_poped = stack[-1]
                        dp[left_first_big_of_poped] = max(dp[left_first_big_of_poped], dp[poped] + 1)
            stack.append(i)
            # print(i, dp, stack)
        return max(dp[:-1]) # 去掉最后一个inf在的位置的dp值

class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        n=len(arr)
        dp=[1 for i in range(n)]
        p=[]
        for idx,x in enumerate(arr):
            p.append((x,idx))
        p.sort(reverse=True)
        for i in range(n):
            idx=p[i][1]
            for j in range(idx+1,min(n,d+idx+1)):
                if arr[j]>=arr[idx]: break
                dp[j]=max(dp[j],dp[idx]+1)
            for j in range(idx-1,max(-1,idx-d-1),-1):
                if arr[j]>=arr[idx]: break
                dp[j]=max(dp[j],dp[idx]+1)
        return max([dp[i] for i in range(n)])

from functools import lru_cache
class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        
        lim = len(arr)
        @lru_cache(None)
        def r(i):
            
            
            tmp = [0]
            for j in range(i-1,i-d-1,-1):
                if j<0:break
                if arr[j]<arr[i]:
                    tmp.append(1+r(j))
                else:
                    break
                    
            
            for j in range(i+1,i+d+1):
                if j>=lim:break
                if arr[j]<arr[i]:
                    tmp.append(1+r(j))
                else:
                    break
            
            return max(tmp)
        
        
        mx = 0
        for i in range(0,lim):
            val = 1+r(i)
            if val>mx:mx = val
                
        return mx

class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        @lru_cache(None)
        def jump(mid):
            left = max(mid - d, 0)
            right = min(mid + d, len(arr) - 1)
            
            res = 1
            for i in range(mid - 1, left - 1, -1):
                if arr[i] >= arr[mid]:
                    break
                res = max(res, jump(i) + 1)
            for i in range(mid + 1, right + 1):
                if arr[i] >= arr[mid]:
                    break
                res = max(res, jump(i) + 1)
            return res
        
        res = [1] * len(arr)
        for i in range(len(arr)):
            res[i] = jump(i)
        return max(res)

import functools

class Solution:
    def maxJumps(self, arr, d: int) -> int:

        @functools.lru_cache(None)
        def helper(i):
            ans = 1
            for index in range(i + 1, min(len(arr), i + d + 1)):
                if arr[i] > arr[index]:
                    ans = max(ans,1 + helper(index))
                else:
                    break

            for index in range(i - 1, max(-1, i - d - 1),-1):
                if arr[i] > arr[index]:
                    ans = max(ans,1 + helper(index))
                else:
                    break

            return ans

        maxJumps = 1
        for i in range(len(arr)):
            maxJumps = max(maxJumps, helper(i))

        return maxJumps


class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        
        l = []
        n = len(arr)
        for i in range(n):l.append([arr[i], i])
        l.sort()
        l = [i[1] for i in l]
        
        dp = [1] * n
        for i in l:
            for j in range(i + 1, min(n, i + d + 1)):
                if arr[i] > arr[j]:dp[i] = max(dp[i], dp[j] + 1)
                else:break
            for j in range(i - 1, max(-1, i - d -1), -1):
                if arr[i] > arr[j]:dp[i] = max(dp[i], dp[j] + 1)
                else:break
        return max(dp)

import functools
class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        
        @functools.lru_cache(None)
        def check_i(inow) :
            max_son = 0
            for i in range(1, min(d+1, len(arr)-inow)) :
                if arr[inow+i] >= arr[inow] :
                    break
                max_son = max(max_son, check_i(inow + i))
            for i in range(1, min(d+1, inow+1)) :
                if arr[inow-i] >= arr[inow] :
                    break
                max_son = max(max_son, check_i(inow - i))
            
            return max_son+1
            
        
        return max([check_i(i) for i in range(len(arr))])
            
        
        


class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        # dp
        # n = len(arr)
        # res = [0] * n
        # def dp(i):
        #     if res[i]:
        #         return res[i]
        #     res[i] = 1
        #     for di in [-1, 1]:
        #         for j in range(i+di, i+d*di+di, di):
        #             if not (0 <= j < n and arr[j] < arr[i]):
        #                 break
        #             res[i] = max(res[i], dp(j) + 1)
        #     return res[i]
        # return max(map(dp, range(n)))
        n = len(arr)
        dp = [1] * n
        for a, i in sorted([a, i] for i, a in enumerate(arr)):
            for di in [-1, 1]:
                for j in range(i+di, i+d*di+di, di):
                    if not (0 <= j < n and arr[j] < arr[i]):
                        break
                    dp[i] = max(dp[i], dp[j] + 1)
        return max(dp) 



# 1340. Jump Game V
# 20201003 这个题目，也只有用栈解决最快


class Solution:  # Decreasing Stack + DP （单调栈 DP）

    def maxJumps(self, arr, d):
        n = len(arr)
        dp = [1] * (n + 1)
        stack = []
        for i, a in enumerate(arr + [float('inf')]):
            while stack and arr[stack[-1]] < a:
                L = [stack.pop()]
                while stack and arr[stack[-1]] == arr[L[0]]:
                    L.append(stack.pop())
                for j in L:
                    if i - j <= d:
                        dp[i] = max(dp[i], dp[j] + 1)
                    if stack and j - stack[-1] <= d:
                        dp[stack[-1]] = max(dp[stack[-1]], dp[j] + 1)
            stack.append(i)
            
        return max(dp[:-1])
    


class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        N = len(arr)
        
        @lru_cache(None)
        def rec(idx):
            if not 0 <= idx < N:
                return -inf
            # print(idx)
            ans = 1
            for i in range(idx-1, idx-d-1, -1):
                if i < 0 or arr[i] >= arr[idx]:
                    break
                ans = max(ans, rec(i) + 1)
            
            for i in range(idx+1, idx+d+1):
                if i >= N or arr[i] >= arr[idx]:
                    break
                ans = max(ans, rec(i) + 1)
            
            return ans
        
        ans = 0
        for i in range(N):
            ans = max(ans, rec(i))
        
        return ans

class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        
        @lru_cache(None)
        def dfs(i):
            if i==0 and i+1<len(arr):
                if arr[i]<=arr[i+1]:
                    return 1
            elif i==len(arr)-1 and i-1>=0:
                if arr[i]<=arr[i-1]:
                    return 1
            elif i-1>=0 and i+1<len(arr) and arr[i]<=arr[i-1] and arr[i]<=arr[i+1]:
                return 1
            
            left_step = 1
            for j in range(i+1, i+d+1):
                if j>=len(arr) or arr[j]>=arr[i]:
                    break
                left_step = max(left_step, 1+dfs(j))
            right_step = 1          
            for j in range(i-1, i-d-1, -1):
                if j<0 or arr[j]>=arr[i]:
                    break
                right_step = max(right_step, 1+dfs(j))
            return max(left_step, right_step)
                
        max_step = 0
        for i in range(len(arr)):
            max_step = max(max_step, dfs(i))
            # print(dfs(i))
        return max_step
                
        
        
        
        
#         d限定了可能跳的最大步长
#         在步长范围内，跳的距离必须满足中间不能有大于自己的值
#         返回可能到达的最多的下标
        
#         每个位置有自己可能调到的最多下标
#         比如6-->4
#         14-》8-》6 或者14-》6-》4 
#         长度为1000
#         按照高度大小，求解初始跳的步长
#         最终一定是跳到一个山谷或者两端的位置
#         dp[i]: 当位置到达下标i时，可能跳到的最多下标，对于山谷或者两端位置而言，初始值为1


class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        from functools import lru_cache

        n = len(arr)

        @lru_cache(maxsize=None)
        def f(i):
            res = 1
            for j in range(i + 1, min(i + d + 1, n)):
                if arr[j] < arr[i]:
                    res = max(res, 1 + f(j))
                else:
                    break
            for j in range(i - 1, max(-1, i - d - 1), -1):
                if arr[j] < arr[i]:
                    res = max(res, 1 + f(j))
                else:
                    break
            return res

        return max(f(_) for _ in range(n))

class Solution:
    def maxJumps(self, A: List[int], d: int) -> int:
        n = len(A)
        @lru_cache(None)
        def helper(i):
            ans = 1            
            l = max(0,i-d)
            r = min(n-1,i+d)
            #print(i,l,r)
        
            for j in reversed(range(l,i)):
                if(A[j]<A[i]):
                    ans = max(ans,1 + helper(j))
                else:
                    break
            for j in range(i+1,r+1):
                if(A[j]<A[i]):
                    ans = max(ans,1 + helper(j))
                else:
                    break
            
            return ans
        
        ans = max([helper(i) for i in range(n)])
        return ans

class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        sorted_indexes = sorted(range(len(arr)), key = lambda i:arr[i])
        # print(sorted_indexes)
        n = len(arr)
        dp = [1] * n
        
        def get_neighs(cur):
            neighs = []
            for i in range(cur + 1, min(cur + d + 1, n)):
                if arr[i] < arr[cur]:
                    neighs.append(i)
                else:
                    break
            for i in range(cur - 1, max(cur - d - 1, -1), -1):
                if arr[i] < arr[cur]:
                    neighs.append(i)
                else:
                    break
            return neighs
        
        for cur in sorted_indexes:
            neighs = get_neighs(cur)
            for neigh in neighs:
                dp[cur] = max(dp[cur], dp[neigh] + 1)
        return max(dp)

class Solution:
    def maxJumps2(self, arr: List[int], d: int) -> int:
        n = len(arr)
        res = [0] * n
        
        def dp(i):
            if res[i] > 0:
                return res[i]
            res[i]=1 # at least itself
            
            for di in [-1, 1]:
                for j in range(i+di, i+d*di+di, di):
                    # di=-1, j in range(i-1, i-d-1, -1) which is from i-1 to i-2 to ... i-d (d positions, all are reachable)
                    # di=1, j in range(i+1, i+d+1, 1), which is from i+1 to i+2 to ... i+d ( d positions, all are reachable)
                    if not (0<=j<n and arr[j] < arr[i]): # if j<0 or j>=n or arr[j] >= arr[i]: break
                        break
                    res[i] = max(res[i], dp(j) + 1)
                    
            return res[i]
        
        return max(map(dp, range(n)))
    
    def maxJumps1(self, arr, d): # 最直观的dp方法！递归调用+记忆化保存
        n = len(arr)
        res = [0] * n
        
        def dp(i):
            if res[i] > 0: return res[i]
            res[i] = 1
            
            for j in range(i+1, i+d+1):
                if j>=n or arr[j] >= arr[i]:
                    break
                res[i] = max(res[i], dp(j) + 1)
            
            for j in range(i-1, i-d-1, -1):
                if j<0 or arr[j] >= arr[i]:
                    break
                res[i] = max(res[i], dp(j) + 1)
            return res[i]
        return max(dp(i) for i in range(n))
    
    def maxJumps(self, arr, d):
        n = len(arr)
        dp = [1] * n
        for a, i in sorted([a, i] for i, a in enumerate(arr)):
            for di in [-1, 1]:
                for j in range(i + di, i + d*di+di, di):
                    if not (0<=j<n and arr[j] < arr[i]):
                        break
                    dp[i] = max(dp[i], dp[j] + 1)
        return max(dp)

class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        hp = [(v, i) for i, v in enumerate(arr)]
        heapq.heapify(hp)
        dp = [0] * len(arr)
        res = 0
        while hp:
            h, i = heapq.heappop(hp)
            tmp = 1
            for j in range(i - 1, i - 1 - d, -1):
                if j < 0 or arr[j] >= arr[i]:
                    break
                tmp = max(tmp, dp[j] + 1)
            for j in range(i + 1, i + 1 + d):
                if j >= len(arr) or arr[j] >= arr[i]:
                    break
                tmp = max(tmp, dp[j] + 1)
            dp[i] = tmp
        return max(dp)


class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        dp = [1] * len(arr)
        a = []
        for idx, val in enumerate(arr):
            a.append((val, idx))
        a.sort()
        print(a)
        for _, idx in a:
            
            for i in range(1, d+1):
                if idx+i<len(arr) and arr[idx+i]<arr[idx]:
                    dp[idx] = max(dp[idx], dp[idx+i]+1)
                else:
                    break
            for i in range(1, d+1):
                if 0<=idx-i and arr[idx-i]<arr[idx]:
                    dp[idx] = max(dp[idx], dp[idx-i]+1)
                else:
                    break
        return max(dp)
                


class Solution:
    def maxJumps(self, A: List[int], d: int) -> int:
        n = len(A)
        dp = [1] * (n + 1)
        stack = []
        for i, a in enumerate(A + [float('inf')]):
            while stack and A[stack[-1]] < a:
                L = [stack.pop()]
                while stack and A[stack[-1]] == A[L[0]]:
                    L.append(stack.pop())
                for j in L:
                    if i - j <= d:
                        dp[i] = max(dp[i], dp[j] + 1)
                    if stack and j - stack[-1] <= d:
                        dp[stack[-1]] = max(dp[stack[-1]], dp[j] + 1)
            stack.append(i)
        return max(dp[:-1])


class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        #top-down dp
        res = [1] * len(arr)
        for a, i in sorted([a, i] for i, a in enumerate(arr)):
            for di in [-1, 1]:
                for j in range(i + di, i + d * di + di, di):
                    if not (0 <= j < len(arr) and arr[j] < arr[i]): break
                    res[i] = max(res[i], 1 + res[j])
        return max(res)


class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        dp = [0] * len(arr)
        path = {i: [(i, arr[i])] for i in range(len(arr))}
        def jump(i):
            nonlocal dp, path
            if dp[i] != 0:
                return dp[i]
            left, right = 0, 0
            nl, nr = i, i
            for j in range(i+1, i+d+1):
                if j >= len(arr):
                    break
                if arr[j] < arr[i]:
                    t= jump(j)
                    if right < t:
                        right = t
                        nr = j
                else:
                    break
            for j in range(i-1, i-d-1, -1):
                if j < 0:
                    break
                if arr[j] < arr[i]:
                    t = jump(j)
                    if left < t:
                        left = t
                        nl = j
                else:
                    break
            if left < right and right > 0:
                path[i] += path[nr]
            elif left >= right and left > 0:
                path[i] += path[nl]
            dp[i] = max(left, right) + 1
            return dp[i]
        
        ans = 0
        for i in range(len(arr)):
            jump(i)
            # print(i, path[i])
            ans = max(ans, dp[i])
        return ans

import functools

class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        
        @functools.lru_cache(None)
        def jump(index):
            res = 0
            for direction in [-1, 1]:
                for x in range(1, d + 1):
                    j = index + x * direction
                    if 0 <= j < len(arr) and arr[j] < arr[index]:
                        res = max(res, jump(j))
                    else:
                        break
            return res + 1
        return max(jump(index) for index in range(len(arr)))

class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        N = len(arr)
        dp = [None]* N
        def cdp(i):
            if dp[i] != None:
                return dp[i]
            dp[i] = 1
            for j in range(i-1,max(0, i-d) -1 , -1):
                if arr[j] >= arr[i]:
                    break
                dp[i] = max(dp[i] , 1 + cdp(j))
            for j in range(i+1,min(N-1, i+d) +1):
                if arr[j] >= arr[i]:
                    break
                dp[i] = max(dp[i] , 1 + cdp(j))
            return dp[i]
        
        for i in range(N):
            cdp(i)
        return max(dp)


from functools import lru_cache 
class Solution:
    def maxJumps(self, arr, d):
        n = len(arr)
        @lru_cache(maxsize = None)
        def findMaxReach(index):
            best = 1
            for i in range(1, d + 1):
                curIndex = index - i
                if 0 <= curIndex < n and arr[curIndex] < arr[index]:
                    best = max(findMaxReach(curIndex) + 1, best)
                else:
                    break
            for i in range(1, d + 1):
                curIndex = index + i
                if 0 <= curIndex < n and arr[curIndex] < arr[index]:
                    best = max(findMaxReach(curIndex) + 1, best)
                else:
                    break
            return best
        ans = 0
        for i in range(n):
            ans = max(findMaxReach(i), ans)
        return ans


class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        N = len(arr)
        dp = [None]* N
        def cdp(i):
            if dp[i] !=None:
                return dp[i]
            dp[i] = 1
            for j in range(i-1, max(0, i-d) -1 , -1):
                if arr[j] >= arr[i]:
                    break
                dp[i] = max(dp[i] , 1 + cdp(j))
            for j in range(i+1, min(N-1, i+d) +1 ):
                if arr[j] >= arr[i]:
                    break
                dp[i] = max(dp[i] , 1 + cdp(j))
            return dp[i]
        for i in range(N):
            cdp(i)
        return max(dp)


from functools import lru_cache


class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        n = len(arr)

        @lru_cache(maxsize=None)
        def jump(i):
            res = 1

            def visit(rng):
                nonlocal res
                for j in rng:
                    if not 0 <= j < n or arr[j] >= arr[i]:
                        break
                    res = max(res, 1 + jump(j))

            visit(range(i - 1, i - d - 1, -1))
            visit(range(i + 1, i + d + 1))
            return res

        return max([jump(i) for i in range(n)])

class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        dp = [0 for i in range(len(arr))]
        
        def findMaxJumps(i):
            if dp[i]!=0:
                return dp[i]
            else:
                ans = 1
                for j in range(i+1, min(i+d+1, len(arr))):
                    if (arr[j]>=arr[i]):
                        break
                    ans = max(ans, 1 + findMaxJumps(j))
                for j in range(i-1, max(i-d,0)-1, -1):
                    if (arr[j]>=arr[i]):
                        break
                    ans = max(ans, 1+ findMaxJumps(j))
                dp[i] = ans 
                return ans
            
        ans = 1    
        for i in range(len(arr)):
            ans = max(ans, findMaxJumps(i))
        return ans
            
                
            
            



# 1340. Jump Game V

class Solution2: # bottom-up dp
    # Time complexity O(NlogN + ND), where we are given D <= N
    # Space complexity O(N) for dp
    def maxJumps(self, arr, d):
        n = len(arr)
        dp = [1] * n
        for a, i in sorted([a, i] for i, a in enumerate(arr)):
            for di in [-1, 1]:
                for j in range(i+di, i+di+d*di, di):
                    if not (0 <= j < n and arr[j] < arr[i]): 
                        break
                    dp[i] = max(dp[i], dp[j] + 1)
        return max(dp)


class Solution:
    
# All element are pushed in and poped from stack1&2 only once, 
# strick O(N) time. 复杂度严格符合O(N)。

# Decreasing Stack + DP
# Use a stack to keep the index of decreasing elements.
# Iterate the array A. When we meet a bigger element a, 
# we pop out the all indices j from the top of stack, 
# where A[j] have the same value.

# Then we update dp[i] and dp[stack[-1]].

# Since all indices will be pushed and popped in stack, 
# appended and iterated in L once,
# the whole complexity is guaranteed to be O(N).

# All element are pushed in and poped from stack1&2 only once, strick O(N) time.
# Time complexity O(N); Space complexity O(N)
# Python runtime 120ms, beats 100%

    def maxJumps(self, arr, d):
        n = len(arr)
        dp = [1] * (n + 1)
        stack = []
        for i, a in enumerate(arr + [float('inf')]):
            while stack and arr[stack[-1]] < a:
                L = [stack.pop()]
                while stack and arr[stack[-1]] == arr[L[0]]:
                    L.append(stack.pop())
                for j in L:
                    if i - j <= d:
                        dp[i] = max(dp[i], dp[j] + 1)
                    if stack and j - stack[-1] <= d:
                        dp[stack[-1]] = max(dp[stack[-1]], dp[j] + 1)
            stack.append(i)
        return max(dp[:-1])
    
    
class Solution1: # top-down dp
    # Time complexity O(ND)
    # Space complexity O(N) for dp
    def maxJumps(self, arr: List[int], d: int) -> int:
        
        n = len(arr)
        res = [0] * n
        
        def dp(i):
            if res[i]: return res[i]
            res[i] = 1
            for di in [-1, 1]:
                for j in range(i+di, i+di+d*di, di):
                    if not (0 <= j < n and arr[j] < arr[i]):
                        break 
                    res[i] = max(res[i], dp(j)+1)
            return res[i]
        
        return max(list(map(dp, list(range(n))))) 
    
    # range(0, n) as input of dp func, then get the max of their results


class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        sorted_indexes = sorted(range(len(arr)), key = lambda i:arr[i])
        n = len(arr)
        dp = [1] * n
        
        def get_neighs(cur):
            neighs = []
            directions = [1, -1]
            for dire in directions:
                for i in range(cur + dire, cur + (d + 1) * dire, dire):
                    if i < 0 or i >= n:
                        break
                    if arr[i] >= arr[cur]:
                        break
                    neighs.append(i)
            return neighs
        
        for cur in sorted_indexes:
            for neigh in get_neighs(cur):
                dp[cur] = max(dp[cur], dp[neigh] + 1)
        return max(dp)

class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        n=len(arr)
        if n==1 or d==0:
            return 1
        e=[[]for i in range(n)]
        for i in range(0,n):
            for j in range(i-1,max(0,i-d)-1,-1):
                if arr[j]<arr[i]:
                    e[i].append(j)
                else :
                    break;
            for j in range(i+1,min(n-1,i+d)+1):
                if arr[j]<arr[i]:
                    e[i].append(j)
                else :
                    break;
        ans=1
        queue=[]
        cnt=[1for i in range(n)]
        for i in range(0,n):
            queue.append([arr[i],i])
        queue.sort()
        for i in range(0,n):
            u=queue[i][1]
            for v in e[u]:
                cnt[u]=max(cnt[u],cnt[v]+1)
            ans=max(ans,cnt[u])
        return ans


class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        sorted_indexes = sorted(range(len(arr)), key = lambda i:arr[i])
        n = len(arr)
        dp = [1] * n
        
        def get_neighs(cur):
            neighs = []
            directions = [1, -1]
            for dire in directions:
                for i in range(cur + dire, cur + (d + 1) * dire, dire):
                    if i < 0 or i >= n:
                        break
                    if arr[i] >= arr[cur]:
                        break
                    neighs.append(i)
            return neighs
        
        for cur in sorted_indexes:
            neighs = get_neighs(cur)
            for neigh in neighs:
                dp[cur] = max(dp[cur], dp[neigh] + 1)
        return max(dp)

class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        n = len(arr)
        
        @lru_cache(None)
        def dfs(i):
            left, right = i, i
            max_range = 1
            while left - 1 >= 0 and arr[left - 1] < arr[i] and left - 1 >= i - d:
                left -= 1
            while right + 1 < n and arr[right + 1] < arr[i] and right + 1 <= i + d:
                right += 1
            
            for nxt in range(left, right + 1):
                if nxt != i:
                    max_range = max(max_range, 1 + dfs(nxt))
            
            return max_range
            
            
        
        return max(dfs(i) for i in range(n))

class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        v = []  
        n = len(arr)
        for i in range(n):
            v.append((arr[i], i))
        v = sorted(v)
        
        f = [-1] * n
        ans = -1
        for i in range(n):
            idx = v[i][1]
            f[idx] = 1
            for j in range(1, d+1):
                if idx - j >= 0 and arr[idx - j] < arr[idx]:
                    f[idx] = max(f[idx], f[idx - j] + 1)
                else:
                    break
            for j in range(1, d+1):
                if idx + j < n and arr[idx + j] < arr[idx]:
                    f[idx] = max(f[idx], f[idx + j] + 1)
                else:
                    break
            ans = max(ans, f[idx])
        
        return ans

def bfs(arr,i,d,memo):
    
    if i in memo:
        return memo[i]
    
    res = 1
    for j in range(max(i-1,0),max(i-d-1,-1),-1):
        if arr[j]>=arr[i]: break
        res = max(res,bfs(arr,j,d,memo)+1)
    
    for j in range(i+1,min(i+d+1,len(arr))):
        if arr[j]>=arr[i]: break
        res = max(res,bfs(arr,j,d,memo)+1)
        
    #print(i,res)
           
    memo[i] = res
    return res

class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        memo = dict()
        return max( bfs(arr,i,d,memo) for i in range(len(arr)) )       


class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        N = len(arr)
        dp = [None] * N
        def cdp(i):
            if dp[i]:
                return dp[i]
            dp[i]=1
            for j in range(i-1, max(0, i-d)-1, -1):
                if arr[j] >= arr[i]:
                    break
                dp[i] = max(dp[i] , 1 + cdp(j))
            for j in range(i+1, min(N-1, i+d)+1, +1):
                if arr[j] >= arr[i]:
                    break
                dp[i] = max(dp[i] , 1 + cdp(j))
            return dp[i]
        for i in range(N):
            cdp(i)
        return max(dp)


class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        n = len(arr)
        dp = [1 for i in range(n)]
        
        @lru_cache(None)
        def rec(i):
            j=1
            while(j<=d and i-j>=0 and arr[i-j]<arr[i]):
                dp[i] = max(dp[i], 1+rec(i-j))
                j += 1
                
            j=1
            while(j<=d and i+j<n and arr[i+j]<arr[i]):
                dp[i] = max(dp[i], 1+rec(i+j))
                j += 1
            return dp[i]
        for k in range(n): rec(k)
        return max(dp)
        


class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        n = len(arr)
        res = [1] * n
        for a, i in sorted([a, i] for i, a in enumerate(arr)):
            for di in [-1, 1]:
                for j in range(i + di, i + d * di + di, di):
                    if not (0 <= j < n and arr[j] < arr[i]):
                        break
                    res[i] = max(res[j] + 1, res[i])
        return max(res)

class Solution:
  def maxJumps(self, arr: List[int], d: int) -> int:
    # stack, TC: O(N), SC: O(N).
    A, n = arr, len(arr)
    # stack is index with decreasing of values, pending jumpping from right, being popped when meet next wall on right.
    s, stack = [1] * (n + 1), []
    for i, x in enumerate(A + [float('inf')]):
      while stack and A[stack[-1]] < x:
        queue = [stack.pop()]
        while stack and A[stack[-1]] == A[queue[-1]]:
          queue.append(stack.pop())
        # j is min between stack[-1] and i, reverse jump up to stack[-1] and i
        for j in queue:
          if i - j <= d:
            s[i] = max(s[i], s[j] + 1)
          if stack and j - stack[-1] <= d:
            s[stack[-1]] = max(s[stack[-1]], s[j] + 1)
      stack.append(i)
    return max(s[:-1])

class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        
        visited = {}
        arrLen = len(arr)
        
        def check(i0):
            if i0 in visited:
                return visited[i0]
            di = 1
            preV = 0
            subAns = 1
            while di <= d and i0+di < arrLen and arr[i0+di] < arr[i0]:
                if arr[i0+di] >= preV:
                    subAns = max(subAns, 1 + check(i0 + di))
                preV = max(preV, arr[i0+di])
                di += 1

            di = 1
            preV = 0
            while di <= d and i0-di >= 0 and arr[i0-di] < arr[i0]:
                if arr[i0-di] >= preV:
                    subAns = max(subAns, 1 + check(i0 - di))
                preV = max(preV, arr[i0-di])
                di += 1

            visited[i0] = subAns
            return subAns
        
        ans = 1
        for i in range(arrLen):
            ans = max(ans, check(i))
        
        # print(visited)
        
        return ans

class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        N = len(arr)
        dp = [None]* N
        def cdp(i):
            if dp[i] != None:
                return dp[i]
            dp[i] = 1
            for j in range(i-1, max(0,i-d)-1,-1):
                if arr[j]>= arr[i]:
                    break
                dp[i] = max(dp[i] , 1+cdp(j))
            for j in range(i+1, min(N-1,i+d)+1):
                if arr[j]>= arr[i]:
                    break
                dp[i] = max(dp[i] , 1+cdp(j))
            return dp[i]
        for i in range(N):
            cdp(i)
        return max(dp)


class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        res = 0
        n = len(arr)
        self.m = [0] * n
        
        for i in range(n):
            ans = self.dfs(arr, d, i)
            res = max(ans, res)
        return res
    
    
    def dfs(self, arr, d, i):
        res = 1
        if self.m[i] != 0:
            return self.m[i]
        
        for k in range(1, d+1):
            if i + k >= len(arr):
                break
            if arr[i+k] >= arr[i]:
                break
            ans = self.dfs(arr, d, i+k) + 1
            if ans > res:
                res = ans

        for k in range(1, d+1):
            if i - k < 0:
                break
            if arr[i-k] >= arr[i]:
                break
            ans = self.dfs(arr, d, i-k) + 1
            if ans  > res:
                res = ans 
        self.m[i] = res
        return res

class Solution:
    def maxJumps(self, A: List[int], d: int) -> int:
        n = len(A)
        dp = [1] * n
        for a, i in sorted([a, i] for i, a in enumerate(A)):
            j = i - 1
            while j >= 0 and A[j] < A[i] and i - j <= d:
                dp[i] = max(dp[i], dp[j] + 1)
                j -= 1
            j = i + 1
            while j < n and A[j] < A[i] and j - i <= d:
                dp[i] = max(dp[i], dp[j] + 1)
                j += 1
        return max(dp)

class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        n = len(arr)
        if(n<=1):
            return n
        visited = [False for i in range(n)]
        L_neighbor = {}
        R_neighbor = {}
        #limit = {}
        
        for i in range(n):
            L_neighbor[i] = i
            R_neighbor[i] = i
            
        dec = deque()
        dec.append(0)
        for i in range(1, n):
            while(len(dec)>0):
                if(dec[0]<i-d):
                    dec.popleft()
                else:
                    break
            while(len(dec)>0):
                if(arr[dec[len(dec)-1]]<arr[i]):
                    dec.pop() 
                else:
                    break
            if(len(dec)==0):
                L_neighbor[i] = max(i-d, 0)
                dec.append(i)
            else:
                L_neighbor[i] = max(dec[len(dec)-1]+1, i-d, 0)
                dec.append(i)
        
        dec = deque()
        dec.append(n-1)
        for i in range(n-2, -1, -1):
            while(len(dec)>0):
                if(dec[0]>i+d):
                    dec.popleft()
                else:
                    break
            
            while(len(dec)>0):
                if(arr[dec[len(dec)-1]]<arr[i]):
                    dec.pop()
                else:
                    break
            if(len(dec)==0):
                R_neighbor[i] = min(i+d, n-1)
                dec.append(i)
            else:
                R_neighbor[i] = min(dec[len(dec)-1]-1, i+d, n-1)
                dec.append(i)
        res = 0
        limit = [0 for i in range(n)]
        
        for i in range(n):
            self.maxJumpDFS(i, arr, L_neighbor, R_neighbor, visited, limit)
        
        for i in range(n):
            if(res<limit[i]):
                res = limit[i]
        
        return res
      
    
    def maxJumpDFS(self, start, arr, L_neighbor, R_neighbor, visited, limit):
        if(visited[start]):
            return limit[start]
        else:
            currmax = 0
            for i in range(L_neighbor[start], R_neighbor[start]+1):
                if(i==start):
                    continue
                curr = self.maxJumpDFS(i, arr, L_neighbor, R_neighbor, visited, limit)
                if(currmax<curr):
                    currmax = curr
            visited[start] = True
            limit[start] = currmax + 1
            return limit[start]
                
                
            
        
        
        
        
        
        
        
        
                


class Solution:
    
    def maxJumps(self, arr: List[int], d: int) -> int:
        maxPath = 0
        memory = {i:0 for i in range(len(arr))}
        for i in range(len(arr)):
            maxPath = max(maxPath, self.dfs(i, d, arr, len(arr), memory))
        return maxPath
    def dfs(self, index, d, arr, arrLen, memory):
        if memory[index] != 0:
            return memory[index]
        
        currentMax = 0
        for i in range(index+1, index +d +1):
            if i >= arrLen or arr[index] <= arr[i]:
                break
            currentMax = max(currentMax, self.dfs(i, d, arr, arrLen, memory))
        
        for i in range(index-1, index - d - 1, -1):
            if i < 0 or arr[index] <= arr[i]:
                break
            currentMax = max(currentMax, self.dfs(i, d, arr, arrLen, memory))
            
        memory[index] = currentMax+1
        return memory[index] 
    


class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        n = len(arr)
        i2h = {}
        for i, h in enumerate(arr):
            i2h[i] = (h, i)
        dp = [1] * n
        for h, idx in sorted(i2h.values(), key=lambda hi: hi[0]):
            j = idx + 1
            while j <= min(n - 1, idx + d) and arr[idx] > arr[j]:
                dp[idx] = max(dp[idx], dp[j] + 1)
                j += 1
            j = idx - 1
            while j >= max(0, idx - d) and arr[idx] > arr[j]:
                dp[idx] = max(dp[idx], dp[j] + 1)
                j -= 1     
        return max(dp)
            
    def maxJumps__(self, arr: List[int], d: int) -> int:
        n = len(arr)
        memo = [0] * n
        def dfs(idx):
            if memo[idx]: return memo[idx]
            jump = 1
            j = idx + 1
            while j <= min(n - 1, idx + d) and arr[idx] > arr[j]:
                jump = max(jump, dfs(j) + 1)
                j += 1
            j = idx - 1
            while j >= max(0, idx - d) and arr[idx] > arr[j]:
                jump = max(jump, dfs(j) + 1)
                j -= 1
            memo[idx] = jump
            return jump
        max_val = 0
        for i in range(n):
            max_val = max(max_val, dfs(i))
        return max_val
        
    def maxJumps_(self, arr: List[int], d: int) -> int:
        def backtracking(idx):
            nonlocal memo, max_val
            if idx in memo: return memo[idx]
            lstack = []
            rstack = []
            lbarrier = False
            rbarrier = False
            for i in range(1, d + 1):
                if not lbarrier and idx - i >= 0 and arr[idx - i] < arr[idx]:
                    lstack.append(idx - i)
                else:
                    lbarrier = True
                if not rbarrier and idx + i < len(arr) and arr[idx + i] < arr[idx]:
                    rstack.append(idx + i)
                else:
                    rbarrier = True
            # if idx == 10: print(lstack, rstack)
            ljump = 1
            while lstack:
                lidx = lstack.pop()
                ljump = max(ljump, 1 + backtracking(lidx))
            rjump = 1
            while rstack:
                ridx = rstack.pop()
                rjump = max(rjump, 1 + backtracking(ridx))
            jump = max(ljump, rjump)
            memo[idx] = jump
            max_val = max(max_val, jump)
            return jump
        memo = {}
        max_val = 0
        for i in range(len(arr)):
            backtracking(i)
            
        return max_val

class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        # dp
        n = len(arr)
        res = [0] * n
        def dp(i):
            if res[i]:
                return res[i]
            res[i] = 1
            for di in [-1, 1]:
                for j in range(i+di, i+d*di+di, di):
                    if not (0 <= j < n and arr[j] < arr[i]):
                        break
                    res[i] = max(res[i], dp(j) + 1)
            return res[i]
        return max(map(dp, range(n)))

class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        arr.append(10 ** 6)
        n = len(arr)
        dp = [1] * n
        stack = []
        result = 0
        for i, a in enumerate(arr):
            while stack and arr[stack[-1]] < a:
                for j in range(len(stack) - 2, -1, -1):
                    if arr[stack[j]] != arr[stack[j + 1]]:
                        break
                else:
                    j = -1
                for k in range(len(stack) - j - 1):
                    l = stack.pop()
                    if i - l <= d:
                        dp[i] = max(dp[i], 1 + dp[l])
                    if j >= 0 and l - stack[j] <= d:
                        dp[stack[j]] = max(dp[stack[j]], 1 + dp[l])
            stack.append(i)
        dp.pop()
        return max(dp)


class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        N = len(arr)
        dp = [None]*N
        def cdp(i):
            if dp[i]:
                return dp[i]
            dp[i]=1
            for j in range(i-1,max(0, i-d)-1, -1):
                if arr[j]>=arr[i]:
                    break
                dp[i] = max(dp[i], 1+cdp(j))    
                
            for j in range(i+1,min(N-1, i+d)+1):
                if arr[j]>=arr[i]:
                    break
                dp[i] = max(dp[i], 1+cdp(j))    
            return dp[i]
        
        for i in range(N):
            cdp(i)
        return max(dp)



# 1340. Jump Game V

class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        
        n = len(arr)
        res = [0] * n
        
        def dp(i):
            if res[i]: return res[i]
            res[i] = 1
            for di in [-1, 1]:
                for j in range(i+di, i+di+d*di, di):
                    if not (0 <= j < n and arr[j] < arr[i]):
                        break 
                    res[i] = max(res[i], dp(j)+1)
            return res[i]
        
        return max(list(map(dp, list(range(n))))) 
    
    # range(0, n) as input of dp func, then get the max of their results


class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        n = len(arr)
        jumps = [1] * n
        
        def get_neighs(cur):
            neighs = []
            directions = [1, -1]
            for dire in directions:
                for i in range(cur + dire, cur + (d + 1) * dire, dire):
                    if i < 0 or i >= n:
                        break
                    if arr[i] >= arr[cur]:
                        break
                    neighs.append(i)
            return neighs
        
        @lru_cache(None)
        def dp(cur):
            for neigh in get_neighs(cur):
                jumps[cur] = max(jumps[cur], dp(neigh) + 1)
            return jumps[cur]
        
        for i in range(len(arr)):
            dp(i)
        return max(jumps)

class Solution:
    
    def maxJumps(self, arr: List[int], d: int) -> int:
        
        n = len(arr)
        res = [0] * n
        
        def dp(i):
            if res[i]: return res[i]
            res[i] = 1
            for di in [-1, 1]:
                for j in range(i+di, i+di+d*di, di):
                    if not (0 <= j < n and arr[j] < arr[i]):
                        break 
                    res[i] = max(res[i], dp(j)+1)
            return res[i]
        
        return max(map(dp, range(n)))

class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        

        # do a DFS with memorization
        m = len(arr)
        memo = [-1 for _ in range(m)]

        def dfs(i):
            if memo[i] != -1:
                return memo[i]

            memo[i] = 1
            left = i - 1
            while left >= 0 and i - left <= d and arr[left] < arr[i]:
                memo[i] = max(dfs(left) + 1, memo[i])
                left -= 1

            right = i + 1
            while right < m and right - i <= d and arr[right] < arr[i]:
                memo[i] = max(dfs(right) + 1, memo[i])
                right += 1
            
            return memo[i]
        
        for i in range(m):
            # print(memo)
            dfs(i)
        
        print(memo)
        return max(memo)


# 1340. Jump Game V

class Solution:
    # Time complexity O(ND)
    # Space complexity O(N) for dp
    def maxJumps(self, arr: List[int], d: int) -> int:
        
        n = len(arr)
        res = [0] * n
        
        def dp(i):
            if res[i]: return res[i]
            res[i] = 1
            for di in [-1, 1]:
                for j in range(i+di, i+di+d*di, di):
                    if not (0 <= j < n and arr[j] < arr[i]):
                        break 
                    res[i] = max(res[i], dp(j)+1)
            return res[i]
        
        return max(list(map(dp, list(range(n))))) 
    
    # range(0, n) as input of dp func, then get the max of their results


# Oct 5, while preparing for Microsoft
class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        if not arr:
            return 0

        result = [0] * len(arr)

        def _helper(i: int) -> int:
            if result[i]:
                return result[i]

            result[i] = 1

            j = 1
            while j <= d and i + j < len(arr) and arr[i + j] < arr[i]:
                result[i] = max(result[i], _helper(i + j) + 1)
                j += 1

            j = 1
            while j <= d and i - j >= 0 and arr[i - j] < arr[i]:
                result[i] = max(result[i], _helper(i - j) + 1)
                j += 1

            return result[i]

        for i in range(len(arr)):
            _helper(i)

        return max(result)



# 1340. Jump Game V

class Solution:
    
    def maxJumps(self, arr: List[int], d: int) -> int:
        
        n = len(arr)
        res = [0] * n
        
        def dp(i):
            if res[i]: return res[i]
            res[i] = 1
            for di in [-1, 1]:
                for j in range(i+di, i+di+d*di, di):
                    if not (0 <= j < n and arr[j] < arr[i]):
                        break 
                    res[i] = max(res[i], dp(j)+1)
            return res[i]
        
        return max(map(dp, range(n)))

class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        @lru_cache(None)
        def helper(idx):
            ans = 1
            ub, lb = 1 , 1
            while ub <= d or lb <= d:
                if idx + ub < len(arr) and arr[idx + ub] < arr[idx]:
                    ans = max(ans, 1 + helper(idx + ub))
                    ub += 1
                else: ub = sys.maxsize
                if idx - lb >= 0 and arr[idx - lb] < arr[idx]:
                    ans = max(ans, 1 + helper(idx - lb))
                    lb += 1
                else: lb = sys.maxsize
            return ans
        return max([helper(idx) for idx in range(len(arr))])

class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        arr1=[[i,v]  for i,v in enumerate(arr)]
        arr1.sort(key=lambda x:x[1])
        dp=[0]*len(arr)
        def dfs(start,arr,dp):
            if dp[start]!=0:
                return dp[start]
            dp[start]=1
            for i in range(start-1,max(start-d-1,-1),-1):
                if arr[start]<=arr[i]:
                    break
                dp[start]=max(dp[start],dfs(i,arr,dp)+1)
            for i in range(start+1,min(start+d+1,len(arr))):
                if arr[start]<=arr[i]:
                     break
                dp[start]=max(dp[start],dfs(i,arr,dp)+1)
            return dp[start]
            
        for i in range(len(arr1)):
            dfs(arr1[i][0],arr,dp)
        return max(dp)

class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        max_less_than=[]
        def jump(iter):
            res=[None for i in range(len(arr))]
            stack=deque([]) # stack里的元素要么大，要么新
            for i in iter:
                while stack and abs(i-stack[0])>d: # 清空范围之外的
                    stack.popleft()
                while stack and arr[i]>arr[stack[-1]]: 
                    latest_poped=stack.pop()
                    res[latest_poped]=i
                stack.append(i)
            return res
        max_less_than.append(jump(range(len(arr))))
        max_less_than.append(jump(reversed(range(len(arr)))))   
        @lru_cache(None)
        def dp(i):
            if i is None:
                return 0
            return max(map(dp,[max_less_than[0][i],max_less_than[1][i]]),default=0)+1
        return max(map(dp,range(len(arr))))

class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        memo = [0] * len(arr)
        def jump(i):
            if memo[i]:
                return memo[i]
            ans = 1
            for di in [-1,1]:
                for x in range(1,d+1):
                    j = di *x +i
                    if 0 <= j <len(arr) and arr[j] < arr[i]:
                        ans = max(ans, jump(j)+1)
                    else:
                        break
            memo[i] = ans
            return memo[i]
        ans= 0
        for i in range(len(arr)):
            ans =max(ans, jump(i))
        return ans


from functools import lru_cache
class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        
        @lru_cache(None)
        def jump(idx):
            
            l, r = idx-1, idx+1
            ans, lans, rans = 1, 0, 0
            
            while l >= max(idx-d, 0) and arr[idx] > arr[l]:
                lans = max(lans, jump(l))
                l -= 1
            
            while r <= min(len(arr)-1, idx+d) and arr[idx] > arr[r]:
                rans = max(rans, jump(r))
                r += 1
            
            return ans + max(rans, lans)
        
        ans = 0
        for i in range(len(arr)):
            ans = max(ans, jump(i))
        return ans

class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        def helper(i):
            if cache[i]:
                return cache[i]
            # go right
            numberOfJump = 0
            for j in range(i + 1, i + d + 1):
                if j >= len(arr) or arr[j] >= arr[i]:
                    break
                numberOfJump = max(helper(j), numberOfJump)
            for j in range(i - 1, i - d - 1, -1):
                if j < 0 or arr[j] >= arr[i]:
                    break
                numberOfJump = max(helper(j), numberOfJump)

            cache[i] = 1 + numberOfJump
            return cache[i]

        cache = [0] * len(arr)
        ans = 0
        for i in range(len(arr)):
            ans = max(helper(i), ans)
        return ans



class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        dp = [0] * len(arr)
        def get_dp(i):
            if dp[i] == 0:
                dp[i] = 1
                j = i-1
                while j >= 0 and arr[i] > arr[j] and i-j <= d:
                    dp[i] = max(dp[i], 1+get_dp(j))
                    j -= 1
                j = i+1
                while j < len(arr) and arr[i] > arr[j] and j-i <= d:
                    dp[i] = max(dp[i], 1+get_dp(j))
                    j += 1
            return dp[i]
        max_count = 0
        for i in range(len(arr)):
            max_count = max(max_count, get_dp(i))
        return max_count
                    


class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        memo = [-1] * len(arr)        
        def dfs(i):
            if i < 0 or i >= len(arr):
                return 0
            
            if memo[i] > 0:
                return memo[i]
            
            memo[i] = 1
            for j in reversed(list(range(max(0, i - d), i))):
                if arr[j] >= arr[i]:
                    break
                memo[i] = max(memo[i], dfs(j) + 1)
                
            for j in range(i + 1, min(len(arr), i + d + 1)):
                if arr[j] >= arr[i]:
                    break
                memo[i] = max(memo[i], dfs(j) + 1)
            
            return memo[i]
        
        return max(dfs(i) for i in range(len(arr)))
                
            


class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        dp = {}
        
        def jump(i):
            
            if i in dp:
                return dp[i]
            
            m = 1
            step = 1
            while i + step < len(arr) and step <= d:
                if arr[i] <= arr[i + step]:
                    break
                m = max(m, jump(i + step) + 1)
                step += 1
         
            step = 1
            while i - step >= 0 and step <= d:
                if arr[i] <= arr[i - step]:
                    break
                m = max(m, jump(i - step) + 1)
                step += 1
            
            dp[i] = m
            return m
        
        ans = 0
        for i in range(len(arr)):
            if i not in dp:
                jump(i)
            ans = max(ans, dp[i])
        return ans

from functools import lru_cache
class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        n = len(arr)
        canJumpRight = collections.defaultdict(set)
        deque = collections.deque()
        for i in range(n):
            # print(deque)
            if not deque:
                deque.append(i)
            else:
                if arr[i] < arr[deque[-1]]:
                    deque.append(i)
                else:
                    temp = collections.deque()
                    while deque and arr[deque[-1]] <= arr[i]:
                        curr = deque.pop()
                        # print('pop', curr, deque and i - deque[-1] <= d)
                        if deque and curr - deque[-1] <= d:
                            canJumpRight[deque[-1]].add(curr)
                            for idx in canJumpRight[curr]:
                                if idx-deque[-1]<=d:
                                    canJumpRight[deque[-1]].add(idx)
                    deque.append(i)
        while deque:
            curr = deque.pop()
            if deque and curr - deque[-1] <= d:
                canJumpRight[deque[-1]].add(curr)
                for idx in canJumpRight[curr]:
                    if idx-deque[-1]<=d:
                        canJumpRight[deque[-1]].add(idx)
                # canJump[deque[-1]].update(canJumpRight[curr])
        canJumpLeft = collections.defaultdict(set)
        for i in range(n-1, -1, -1):
            if not deque:
                deque.append(i)
            else:
                if arr[i] < arr[deque[-1]]:
                    deque.append(i)
                else:
                    while deque and arr[deque[-1]] <= arr[i]:
                        curr = deque.pop()
                        if deque and abs(curr - deque[-1]) <= d:
                            canJumpLeft[deque[-1]].add(curr)
                            for idx in canJumpLeft[curr]:
                                if abs(idx-deque[-1])<=d:
                                    canJumpLeft[deque[-1]].add(idx)
                    deque.append(i)
        while deque:
            curr = deque.pop()
            if deque and abs(curr - deque[-1]) <= d:
                canJumpLeft[deque[-1]].add(curr)
                for idx in canJumpLeft[curr]:
                    if abs(idx-deque[-1])<=d:
                        canJumpLeft[deque[-1]].add(idx)
        res = 0
        arr_set = collections.defaultdict(set)
        for i in range(n):
            arr_set[i] = canJumpLeft[i]|canJumpRight[i]
        res = 0
        @lru_cache(None)
        def dfs(curr):
            nonlocal res
            if curr not in arr_set:
                return 1
            local = 0
            for ne in arr_set[curr]:
                local = max(local, dfs(ne))
            res = max(res, local+1)
            return local+1
        for i in range(n):
            dfs(i)
        return res
        


class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        n = len(arr)
        dp = [1] * n
        for a,i in sorted([a,i] for i,a in enumerate(arr)):
            for di in [-1,1]:
                for j in range(i+di, i+d*di+di,di):
                    if 0 <= j <n and arr[j] < arr[i]:
                        dp[i] = max(dp[i],dp[j]+1)
                    else:
                        break
        return max(dp)


class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        n = len(arr)
        memo = [0] * n
        def dfs(idx):
            if memo[idx]: return memo[idx]
            jump = 1
            j = idx + 1
            while j <= min(n - 1, idx + d) and arr[idx] > arr[j]:
                jump = max(jump, dfs(j) + 1)
                j += 1
            j = idx - 1
            while j >= max(0, idx - d) and arr[idx] > arr[j]:
                jump = max(jump, dfs(j) + 1)
                j -= 1
            memo[idx] = jump
            return jump
        max_val = 0
        for i in range(n):
            max_val = max(max_val, dfs(i))
        return max_val
        
    def maxJumps_(self, arr: List[int], d: int) -> int:
        def backtracking(idx):
            nonlocal memo, max_val
            if idx in memo: return memo[idx]
            lstack = []
            rstack = []
            lbarrier = False
            rbarrier = False
            for i in range(1, d + 1):
                if not lbarrier and idx - i >= 0 and arr[idx - i] < arr[idx]:
                    lstack.append(idx - i)
                else:
                    lbarrier = True
                if not rbarrier and idx + i < len(arr) and arr[idx + i] < arr[idx]:
                    rstack.append(idx + i)
                else:
                    rbarrier = True
            # if idx == 10: print(lstack, rstack)
            ljump = 1
            while lstack:
                lidx = lstack.pop()
                ljump = max(ljump, 1 + backtracking(lidx))
            rjump = 1
            while rstack:
                ridx = rstack.pop()
                rjump = max(rjump, 1 + backtracking(ridx))
            jump = max(ljump, rjump)
            memo[idx] = jump
            max_val = max(max_val, jump)
            return jump
        memo = {}
        max_val = 0
        for i in range(len(arr)):
            backtracking(i)
            
        return max_val

import functools

class Solution:
    def maxJumps(self, A, d):
        N = len(A)
        graph = collections.defaultdict(list)
        
        def jump(iterator):
            stack = []
            for i in iterator:
                while stack and A[stack[-1]] < A[i]:
                    j = stack.pop()
                    if abs(i - j) <= d: graph[j].append(i)
                stack.append(i)
        
        jump(range(N))
        jump(reversed(range(N)))
        
        @functools.lru_cache(maxsize=None)
        def height(i):
            return 1 + max(map(height, graph[i]), default=0)
        
        return max(map(height, range(N)))

class Solution:
    def maxJumps(self, arr: List[int], dis: int) -> int:
        res = 1
        d = dict()
        visit = set()
        
        if len(arr) == 1:
            return 1
        
        for i in range(len(arr)):
            if i == 0:
                if arr[i] <= arr[i+1]:
                    d[i] = 1
                    visit.add(i)
            elif i == len(arr) - 1:
                if arr[i] <= arr[i-1]:
                    d[i] = 1
                    visit.add(i)
            else:
                if arr[i] <= arr[i-1] and arr[i] <= arr[i+1]:
                    d[i] = 1
                    visit.add(i)
        
        def dfs(index):
            if index not in visit:
                visit.add(index)
                cur = 1
                for i in range(1, dis+1):
                    if index - i >= 0 and arr[index-i] < arr[index]:
                        temp = dfs(index-i)
                        d[index-i] = temp
                        cur = max(cur, 1 + temp)
                    else:
                        break
                for i in range(1, dis+1):
                    if index + i < len(arr) and arr[index+i] < arr[index]:
                        temp = dfs(index+i)
                        d[index+i] = temp
                        cur = max(cur, 1 + temp)
                    else:
                        break
                return cur
            else:
                return d[index]      
        
        for x in range(len(arr)):
            if x not in visit:
                cur = dfs(x)
                d[x] = cur
                res = max(res, cur)
            else:
                res = max(res, d[x])
        
        return res

class Solution:
    def rec(self, v):
        if self.memo[v]!=-1:
            return self.memo[v]
    
        res = 1
        
        for nv in self.G[v]:
            res = max(res, 1+self.rec(nv))
        
        self.memo[v] = res
        return res
    
    def maxJumps(self, arr: List[int], d: int) -> int:
        n = len(arr)
        self.G = [[] for _ in range(n)]
        
        for i in range(n):
            for j in range(i-1, i-d-1, -1):
                if j<0 or arr[j]>=arr[i]:
                    break
                self.G[i].append(j)
        
            for j in range(i+1, i+d+1):
                if j>=n or arr[j]>=arr[i]:
                    break
                self.G[i].append(j)
        
        self.memo = [-1]*n
        ans = 0
        
        for i in range(n):
            ans = max(ans, self.rec(i))
        
        return ans

class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        ans = dict()
        
        def dfs(idx):
            if idx in ans:
                return
            ans[idx] = 1
            
            i = idx - 1
            while i >= 0 and idx - i <= d and arr[i] < arr[idx]:
                dfs(i)
                ans[idx] = max(ans[idx], ans[i]+1)
                i -= 1
            
            i = idx + 1
            while i < len(arr) and i - idx <= d and arr[i] < arr[idx]:
                dfs(i)
                ans[idx] = max(ans[idx], ans[i]+1)
                i += 1
        
        for i in range(len(arr)):
            dfs(i) 
        print(ans)
        return max(ans.values())

class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        memo = {}
        def solve(i):
            if i in memo:
                return memo[i]
            
            ret = 1
            j = i-1
            while j>=max(0, i-d) and arr[j] < arr[i]:
                ret = max(ret, 1+solve(j))
                j -= 1
            j = i+1
            while j<=min(len(arr)-1, i+d) and arr[j]<arr[i]:
                ret = max(ret, 1+solve(j))
                j += 1
            memo[i] = ret
            return ret
        for i in range(len(arr)):
            solve(i)
        return max(memo.values())


class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        self.memo = {}
        self.result = 0
        for i in range(len(arr)):
            self.dfs(arr, i, d)
        return self.result
        
    
    def dfs(self, arr, index, d):
        if index in self.memo:
            return self.memo[index]
        result = 0
        for dir in [-1, 1]:
            for i in range(1, d + 1):
                j = index + i * dir
                if 0 <= j < len(arr) and arr[index] > arr[j]:
                    result = max(result, self.dfs(arr, j, d))
                else:
                    break
        self.memo[index] = result + 1
        self.result = max(self.result, result + 1)
        return result + 1

class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        N  = len(arr)
        umap = [list() for i in range(N)]
        dp = [-1 for i in range(N)]
        
        def dfs(idx: int) -> int:
            if idx >= N or idx < 0:
                return 0
            
            if dp[idx] != -1:
                return dp[idx]
            
            curr = 0
            for u in umap[idx]:
                curr = max(curr, dfs(u))
            dp[idx] = curr + 1  
            
            return dp[idx]
        
        for i in range(N):
            minIdx = max(0, i-d)
            maxIdx = min(N-1, i+d)
            
            for t in range(i-1, minIdx-1, -1):
                if arr[i] > arr[t]:
                    umap[i].append(t)
                else:
                    break
                    
            for t in range(i+1, maxIdx+1):
                if arr[i] > arr[t]:
                    umap[i].append(t)
                else:
                    break
        
        result = 0
        for i in range(N):
            result = max(result, dfs(i))
            
        return result

class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        a = []
        jump = [0]*len(arr)
        result = 0
        for i in range(len(arr)):
            a.append((i,arr[i]))
        a.sort(key = lambda x:x[1])
        for i in range(len(arr)):
            l = a[i][0] - 1
            r = a[i][0] + 1
            m = 0
            while (l >= 0 and arr[l] < a[i][1] and a[i][0] - l <= d):
                m = max(m,jump[l])
                l -= 1
            while (r < len(arr) and arr[r] < a[i][1] and r - a[i][0] <= d):
                m = max(m, jump[r])
                r += 1
            jump[a[i][0]] = m + 1
            result = max(result, m + 1)
        return result


def max_jump(a, d, memo, i):
    if i in memo:
        return memo[i]
    max_ =0
    for j in range(1, d+1):
        if i + j>=len(a) or a[i+j] >= a[i]:
            break
        max_ = max(max_, max_jump(a,d,memo, i+j))
    for j in range(1, d+1):
        if i - j<0 or a[i-j] >= a[i]:
            break
        max_ = max(max_, max_jump(a,d,memo, i-j))
    memo[i] = max_+1
    return max_+1
class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        memo = {}
        for i in range(len(arr)):
            max_jump(arr, d, memo, i)
        return max(memo.values())


class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        
        def dp(arr,d,dic,i,n):
            
            if(dic[i] != None):
                return dic[i]
            
            
            maximum = 1
            
            upreached = False
            downreached = False
            
            for p in range(1,d+1):
                
                if(i + p < n and not upreached):
                    
                    if(arr[i+p] >= arr[i]):
                        upreached = True
                        
                    else:
                        maximum = max(maximum, 1+dp(arr,d,dic,i+p,n))
                
                if(i-p >= 0 and not downreached):
                    
                    if(arr[i-p] >= arr[i]):
                        downreached = True
                        
                    else:
                        maximum = max(maximum, 1+dp(arr,d,dic,i-p,n))
                
                if(upreached and downreached):
                    break
                
            
            dic[i] = maximum
            
            return maximum
        
        n = len(arr)
        
        dic = [None]*n
        
        maximum = 0
        
        for i in range(n):
            
            maximum = max(maximum,dp(arr,d,dic,i,n))
        
        
        return maximum

class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        dp = [-1 for _ in range(len(arr))]

        def dp_memo(x):
            if dp[x] != -1:
                return dp[x]

            dp[x] = 1
            for y in range(x-1, x-d-1, -1):
                if y < 0 or arr[y] >= arr[x]:
                    break
                dp[x] = max(dp[x], 1 + dp_memo(y))

            for y in range(x+1, x+d+1, +1):
                if y >= len(arr) or arr[y] >= arr[x]:
                    break
                dp[x] = max(dp[x], 1 + dp_memo(y))
            return dp[x]

        for i in range(len(arr)):
            dp_memo(i)
        print(dp)
        return max(dp)