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: MEDIUM
Tags: Dynamic programming

Sorting

Data structures
Skill types: Dynamic programming

Sorting

Data structures

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:
					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, nums: List[int], d: int) -> int:
		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:
						dp[i] = max(dp[i], dp[poped] + 1)
					if stack and poped - stack[-1] <= d:
						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)
		return max(dp[:-1])


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:
				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:
		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:

	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())


class Solution:

	def helper(self, idx):
		if self.dp[idx] != float('inf'):
			return self.dp[idx]
		max_step = 1
		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)
		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)
		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 i >= len(arr):
					break
				if abs(arr[i]) >= abs(arr[index]):
					break
				if arr[i] < 0:
					continue
				left_visited = max(left_visited, helper(arr, i, d, memo))
			for j in range(index - 1, index - d - 1, -1):
				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]
			memo[index] = 1 + max(left_visited, right_visited)
			return memo[index]
		max_visited = 1
		p = False
		memo = {}
		for index in range(len(arr)):
			visited = helper(arr, index, d, memo)
			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
				ans = max(ans, solve(i + node))
			for i in range(1, d + 1):
				if node - i < 0 or arr[node - i] >= arr[node]:
					break
				ans = max(ans, solve(node - i))
			dp[node] = 1 + ans
			return dp[node]
		for i in range(n):
			solve(i)
		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()
			if idx in stepCount and steps <= stepCount[idx]:
				continue
			stepCount[idx] = steps
			maxSteps = max(steps, maxSteps)
			for jumpIdx in range(idx + 1, min(len(arr), idx + d + 1)):
				if arr[jumpIdx] >= arr[idx]:
					break
				bfs.append((jumpIdx, steps + 1))
			for jumpIdx in range(idx - 1, max(0, idx - d) - 1, -1):
				if arr[jumpIdx] >= arr[idx]:
					break
				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


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:
		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:
		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))
		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
			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:
		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)
		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:

	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)))))


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)

		@lru_cache(None)
		def dp(i):
			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))
		return res


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:
		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:
		N = len(arr)

		@lru_cache(None)
		def rec(idx):
			if not 0 <= idx < N:
				return -inf
			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))
		return max_step


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)
			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])
		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 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, 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)
			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


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


class Solution2:

	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:

	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:

	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)))))


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 = [1 for 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:
		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)
	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 = [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:
		(A, n) = (arr, len(arr))
		(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())
				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))
		return ans


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 = {}
		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
			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:
		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)
		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:
		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):
			dfs(i)
		print(memo)
		return max(memo)


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)


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([])
			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]
			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):
			if not deque:
				deque.append(i)
			elif arr[i] < arr[deque[-1]]:
				deque.append(i)
			else:
				temp = collections.deque()
				while deque and arr[deque[-1]] <= arr[i]:
					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)
				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)
		canJumpLeft = collections.defaultdict(set)
		for i in range(n - 1, -1, -1):
			if not deque:
				deque.append(i)
			elif 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


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)
			elif 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)