Monster Factory

source: University of Aizu Programming Contest 2009 3

raw_problem:
Problem B: Monster Factory

株式会社南天堂は, Packet Monster というゲームソフトを発売している. このゲームはモンスターを捕まえ, 育て, 戦わせるという趣旨のもので, 世界中で大人気のゲームであった.

このゲームには従来のゲームには無い特徴があった. このゲームには Red と Green という2つのバージョンがあり, それぞれのゲームで捕まえられるモンスターが異なるのだ. Red でしか捕まえられないモンスターを Green で入手するには, 通信交換というシステムを使う. つまり, 自分のソフト内のモンスターと友達のソフト内のモンスターを交換することができるのだ. このシステムは Packet Monster の人気に大きく貢献していた.

しかし, このゲームのパッケージの製造工程は, 2つのバージョンのために少々複雑になった. パッケージを製造している工場には2つの生産ラインがあり, 片方のラインでは Red を, もう一方のラインでは Green を製造している. 各ラインで製造されたパッケージは, 工場内で一意な製造番号が割り当てられ, 一箇所に集められる. そして以下のような攪拌（かくはん）装置によって混ぜられ, 出荷されるのだ.

Red のパッケージは上側から, Green のパッケージは左側から, ベルトコンベアによってこの攪拌装置に届けられる. 攪拌装置は十字の形をした2本のベルトコンベアから出来ており, "push_down", "push_right" という2つの命令を受け付ける. "push_down"は「上下方向に走るベルトコンベアをパッケージ1個分下方向に動かせ」, "push_right"は「左右方向に走るベルトコンベアをパッケージ1個分右方向に動かせ」という命令である. 攪拌は, Red のパッケージと同じ数の push_down 命令と Green のパッケージの数より１つ多い push_right 命令を, ランダムな順番で実行することによって行われる. ただし, 最初に実行される命令と最後に実行される命令は "push_right" と決まっている. この制約の元では, Red のパッケージの数と攪拌装置の下端に届くパッケージの数が一致し, Green のパッケージの数と攪拌装置の右端に届くパッケージの数が一致する.

攪拌されたパッケージは最終的にベルトコンベアの下端または右端に届き, 届いた順に包装されて出荷される.

以下に, 一連の攪拌の手続きの例を示す.
簡単のため, 1つのパッケージを1文字のアルファベットとして表す.

さて, この工場では不良品の追跡などの目的で, ベルトコンベアの下端・右端に届いたパッケージとその順番を記録している.しかしこの記録にはコストが掛かるため, 工場長は下端に届いたパッケージについてのみ記録を取ることを考えた.右端に届いたパッケージは, 上端・左端に送られるパッケージと下端に届いたパッケージの記録から求められるのではないかと思ったのだ.

工場長を助けて, 右端に届いたパッケージの記録を作成するプログラムを作ってほしい.

Input

入力は複数のデータセットからなる. 入力の終わりは - (ハイフン)１つの行で示される.

1つの入力は3行のアルファベットの大文字・小文字のみを含む文字列からなる.
これらはそれぞれ, Red のパッケージ, Green のパッケージ, 下端に届いたパッケージを表す.1文字のアルファベットが1個のパッケージを表す.大文字と小文字は区別されることに注意せよ.

どの行にも, 同じ文字が2回以上現れることは無い.
1行目と2行目に共通して含まれる文字も存在しない.

問題文中で説明されたケースは, Sample Inputの1つ目の例に対応している.

Output

右端に届いたパッケージを, 届いた順番のとおりに出力せよ.

Sample Input

CBA
cba
cCa
X
ZY
Z
-

Output for the Sample Input

BbA
XY

solutions: ["# AOJ 1036: Monster Factory\n# Python3 2018.7.6 bal4u\n\nwhile True:\n\tin1 = list(input())\n\tif in1[0] == '-': break\n\tin2 = list(input())\n\tout = list(input())\n\tk = in2.pop(0)\n\tans, f = '', True\n\twhile len(in1) or len(in2):\n\t\tif len(out) and out[0] == k:\n\t\t\tk = in1.pop(0)\n\t\t\tdel out[0]\n\t\telse:\n\t\t\tans += k\n\t\t\tif len(in2): k = in2.pop(0)\n\t\t\telse:\n\t\t\t\tf = False\n\t\t\t\tbreak\n\tif f: ans += k\n\tprint(ans)\n", "while True:\n  s1 = list(input())\n  if s1 == [\"-\"]:\n    break\n  s2 = list(input())\n  s1.reverse()\n  s2.reverse()\n  under = list(input())\n  under.reverse()\n  right = []\n  center = s2.pop()\n  while s1 or s2:\n    if under and center == under[-1]:\n      center = s1.pop()\n      under.pop()\n    else:\n      right.append(center)\n      center = s2.pop()\n  if not under:\n    right.append(center)\n  print(\"\".join(right))\n"]

source: aizu

question:
Problem B: Monster Factory

The company Nan Tendou Co., Ltd. is releasing a game software called Packet Monster. This game, which involves catching, nurturing, and battling monsters, was a globally popular game.

This game had a unique feature not found in traditional games. There were two versions of the game, Red and Green, and the monsters that could be caught were different in each game. To obtain a monster that can only be caught in Red while playing Green, one has to use a system called communication trading. In other words, players can exchange the monsters in their own software with those in their friend's software. This system contributed significantly to the popularity of Packet Monster.

However, the manufacturing process of the game's packages became somewhat complicated because of the two versions. The factory where packages are manufactured has two production lines, one for producing Red and one for producing Green. Packages manufactured on each line are given a unique manufacturing number and are collected together in one place within the factory. Then they are mixed using the following blending (kakuhann) device and shipped out.

![image](1.png)

Packages of Red are delivered to the mix-o-matic from the top, and packages of Green from the left, via a conveyor belt. The mix-o-matic consists of two belt conveyors in the shape of a cross and accepts two commands: "push_down" and "push_right". "push_down" means "move the belt conveyor that runs vertically by one package down" and "push_right" means "move the belt conveyor that runs horizontally by one package to the right." Mixing is done by executing a random sequence of the same number of push_down commands as Red packages and one more push_right command than the number of Green packages. However, the first and last executed commands must be "push_right". With this constraint, the number of Red packages matches the number of packages that reach the bottom end of the mixing device, and the number of Green packages matches the number of packages that reach the right end of the mixing device.

The mixed packages eventually arrive at either the bottom end or the right end of the conveyor belt, are then packed in order, and shipped.

Below is an example of a series of mixing procedures.
For simplicity, one package is represented by one alphabet letter.

![image](2.png)

Now, the factory records the packages that reach the bottom and right ends of the conveyer belt and their order for tracking defective products and other purposes. However, this recording process is costly, so the factory manager considered recording only the packages that reached the bottom end. He thought that the record of packages sent to the top and left ends, and the record of packages that reached the bottom end could be used to determine which packages reached the right end.

Help the factory manager by creating a program to record the packages that reach the right end.

Input

The input consists of multiple data sets. The end of the input is indicated by a single hyphen (-) line.

One input consists of three lines of strings containing only uppercase and lowercase alphabet letters.
They represent the Red packages, Green packages, and packages that reached the bottom end, respectively. One alphabet letter represents one package. Note that uppercase and lowercase are distinguished.

In no line does the same letter appear more than once.
There is also no letter that is common to both the first and second lines.

The case explained in the problem text corresponds to the first example in the Sample Input.

Output

Output the packages that reached the right end in the order they arrived.

Sample Input

CBA
cba
cCa
X
ZY
Z
-

Output for the Sample Input

BbA
XY

image_tags:
Linear Data Structure
Linear Data Structure

data_split: test


solutions: ["class Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\t\tdp = [1] * (len(arr) + 1)\n\t\tstack = []\n\t\tfor (i, n) in enumerate(arr + [1000000]):\n\t\t\twhile stack and arr[stack[-1]] < n:\n\t\t\t\tsame_height_idx = [stack.pop()]\n\t\t\t\twhile stack and arr[stack[-1]] == arr[same_height_idx[0]]:\n\t\t\t\t\tsame_height_idx.append(stack.pop())\n\t\t\t\tfor j in same_height_idx:\n\t\t\t\t\tif i - j <= d:\n\t\t\t\t\t\tdp[i] = max(dp[i], dp[j] + 1)\n\t\t\t\t\tif stack and j - stack[-1] <= d:\n\t\t\t\t\t\tdp[stack[-1]] = max(dp[stack[-1]], dp[j] + 1)\n\t\t\tstack.append(i)\n\t\treturn max(dp[:-1])\n", "class Solution:\n\n\tdef maxJumps(self, nums: List[int], d: int) -> int:\n\t\tnums.append(math.inf)\n\t\tdp = [1] * len(nums)\n\t\tstack = []\n\t\tfor (i, cur) in enumerate(nums):\n\t\t\twhile stack and nums[stack[-1]] < cur:\n\t\t\t\tpoped_same_val = [stack.pop()]\n\t\t\t\twhile stack and nums[stack[-1]] == nums[poped_same_val[0]]:\n\t\t\t\t\tpoped_same_val.append(stack.pop())\n\t\t\t\tfor poped in poped_same_val:\n\t\t\t\t\tif i - poped <= d:\n\t\t\t\t\t\tdp[i] = max(dp[i], dp[poped] + 1)\n\t\t\t\t\tif stack and poped - stack[-1] <= d:\n\t\t\t\t\t\tleft_first_big_of_poped = stack[-1]\n\t\t\t\t\t\tdp[left_first_big_of_poped] = max(dp[left_first_big_of_poped], dp[poped] + 1)\n\t\t\tstack.append(i)\n\t\treturn max(dp[:-1])\n", "class Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\t\tn = len(arr)\n\t\tdp = [1] * (n + 1)\n\t\tstack = []\n\t\tfor (i, a) in enumerate(arr + [float('inf')]):\n\t\t\twhile stack and arr[stack[-1]] < a:\n\t\t\t\tL = [stack.pop()]\n\t\t\t\twhile stack and arr[stack[-1]] == arr[L[0]]:\n\t\t\t\t\tL.append(stack.pop())\n\t\t\t\tfor j in L:\n\t\t\t\t\tif i - j <= d:\n\t\t\t\t\t\tdp[i] = max(dp[i], dp[j] + 1)\n\t\t\t\t\tif stack and j - stack[-1] <= d:\n\t\t\t\t\t\tdp[stack[-1]] = max(dp[stack[-1]], dp[j] + 1)\n\t\t\tstack.append(i)\n\t\treturn max(dp[:-1])\n", "class Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\t\tres = 0\n\t\tvisited = {}\n\n\t\tdef dfs(i):\n\t\t\tif i in visited:\n\t\t\t\treturn visited[i]\n\t\t\tstep = 1\n\t\t\ti_right = i + 1\n\t\t\twhile i_right < len(arr) and i_right - i <= d:\n\t\t\t\tif arr[i_right] >= arr[i]:\n\t\t\t\t\tbreak\n\t\t\t\tstep = max(step, 1 + dfs(i_right))\n\t\t\t\ti_right += 1\n\t\t\ti_left = i - 1\n\t\t\twhile i_left >= 0 and i - i_left <= d:\n\t\t\t\tif arr[i_left] >= arr[i]:\n\t\t\t\t\tbreak\n\t\t\t\tstep = max(step, 1 + dfs(i_left))\n\t\t\t\ti_left -= 1\n\t\t\tvisited[i] = step\n\t\t\treturn step\n\t\tfor i in range(len(arr)):\n\t\t\tres = max(res, dfs(i))\n\t\treturn res\n", "class Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\t\tcache = {}\n\n\t\tdef f(i):\n\t\t\tif i in cache:\n\t\t\t\treturn cache[i]\n\t\t\tleft = True\n\t\t\tright = True\n\t\t\tret = 1\n\t\t\tfor step in range(1, d + 1):\n\t\t\t\tm = i - step\n\t\t\t\tif 0 <= m < len(arr) and arr[m] < arr[i] and left:\n\t\t\t\t\tret = max(ret, f(m) + 1)\n\t\t\t\telse:\n\t\t\t\t\tleft = False\n\t\t\t\tm = i + step\n\t\t\t\tif 0 <= m < len(arr) and arr[m] < arr[i] and right:\n\t\t\t\t\tret = max(ret, f(m) + 1)\n\t\t\t\telse:\n\t\t\t\t\tright = False\n\t\t\t\tif not left and (not right):\n\t\t\t\t\tbreak\n\t\t\tcache[i] = ret\n\t\t\treturn ret\n\t\tmm = 0\n\t\tfor i in range(len(arr)):\n\t\t\tfi = f(i) if i not in cache else cache[i]\n\t\t\tmm = max(f(i), mm)\n\t\treturn mm\n", "class Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\t\tn = len(arr)\n\t\tcache = {}\n\n\t\tdef find_max_jumps(i):\n\t\t\tif i in cache:\n\t\t\t\treturn cache[i]\n\t\t\tmax_jumps = 1\n\t\t\tfor dr in [1, -1]:\n\t\t\t\tfor r in range(1, d + 1):\n\t\t\t\t\tif not (0 <= i + dr * r < n and arr[i + dr * r] < arr[i]):\n\t\t\t\t\t\tbreak\n\t\t\t\t\tmax_jumps = max(max_jumps, 1 + find_max_jumps(i + dr * r))\n\t\t\tcache[i] = max_jumps\n\t\t\treturn max_jumps\n\t\tresult = 1\n\t\tfor i in range(n):\n\t\t\tresult = max(result, find_max_jumps(i))\n\t\treturn result\n\nclass Solution111:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\t\tn = len(arr)\n\t\tres = [0] * n\n\n\t\tdef dp(i):\n\t\t\tif res[i]:\n\t\t\t\treturn res[i]\n\t\t\tres[i] = 1\n\t\t\tfor di in [-1, 1]:\n\t\t\t\tfor j in range(i + di, i + di + d * di, di):\n\t\t\t\t\tif not (0 <= j < n and arr[j] < arr[i]):\n\t\t\t\t\t\tbreak\n\t\t\t\t\tres[i] = max(res[i], dp(j) + 1)\n\t\t\treturn res[i]\n\t\treturn max(map(dp, range(n)))\n", "class Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\n\t\t@lru_cache(None)\n\t\tdef dfs(index):\n\t\t\tres = 0\n\t\t\tfor direction in [-1, 1]:\n\t\t\t\tfor jump in range(1, d + 1):\n\t\t\t\t\tj = index + direction * jump\n\t\t\t\t\tif 0 <= j < len(arr) and arr[index] > arr[j]:\n\t\t\t\t\t\tres = max(res, dfs(j))\n\t\t\t\t\telse:\n\t\t\t\t\t\tbreak\n\t\t\treturn res + 1\n\t\treturn max((dfs(i) for i in range(len(arr))))\n", "from typing import List\n\nclass Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\t\tresult = 0\n\t\tmapping = dict()\n\t\tfor (index, value) in enumerate(arr):\n\t\t\tif index not in mapping:\n\t\t\t\tmapping[index] = set()\n\t\t\tfor dd in range(1, d + 1):\n\t\t\t\tif index + dd >= len(arr):\n\t\t\t\t\tbreak\n\t\t\t\tif arr[index + dd] < arr[index]:\n\t\t\t\t\tmapping[index].add(index + dd)\n\t\t\t\telse:\n\t\t\t\t\tbreak\n\t\t\tfor dd in range(1, d + 1):\n\t\t\t\tif index - dd < 0:\n\t\t\t\t\tbreak\n\t\t\t\tif arr[index - dd] < arr[index]:\n\t\t\t\t\tmapping[index].add(index - dd)\n\t\t\t\telse:\n\t\t\t\t\tbreak\n\t\t\tpass\n\t\tcache = dict()\n\n\t\tdef dfs(cache, mapping, root):\n\t\t\tif root in cache:\n\t\t\t\treturn cache[root]\n\t\t\tif root not in mapping:\n\t\t\t\treturn 0\n\t\t\tresult = 0\n\t\t\tfor next in mapping[root]:\n\t\t\t\tresult = max(result, dfs(cache, mapping, next) + 1)\n\t\t\t\tpass\n\t\t\tcache[root] = result\n\t\t\treturn result\n\t\tresult = 1\n\t\tfor i in range(len(arr)):\n\t\t\tresult = max(result, dfs(cache, mapping, i) + 1)\n\t\treturn result\n", "class Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\t\tn = len(arr)\n\t\tmemo = [0] * n\n\n\t\tdef dfs(start):\n\t\t\tif start < 0 or start >= n:\n\t\t\t\treturn 0\n\t\t\tif memo[start] > 0:\n\t\t\t\treturn memo[start]\n\t\t\tvisited[start] = 1\n\t\t\tret = 1\n\t\t\tfor i in range(start - 1, max(0, start - d) - 1, -1):\n\t\t\t\tif arr[i] >= arr[start]:\n\t\t\t\t\tbreak\n\t\t\t\tif visited[i]:\n\t\t\t\t\tcontinue\n\t\t\t\tret = max(ret, dfs(i) + 1)\n\t\t\tfor j in range(start + 1, min(start + d, n - 1) + 1):\n\t\t\t\tif arr[j] >= arr[start]:\n\t\t\t\t\tbreak\n\t\t\t\tif visited[j]:\n\t\t\t\t\tcontinue\n\t\t\t\tret = max(ret, dfs(j) + 1)\n\t\t\tvisited[start] = 0\n\t\t\tmemo[start] = ret\n\t\t\treturn ret\n\t\tret = 1\n\t\tvisited = [0] * n\n\t\tfor i in range(n):\n\t\t\tret = max(dfs(i), ret)\n\t\treturn ret\n", "class Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\n\t\tdef dfs(i):\n\t\t\tif i in cache:\n\t\t\t\treturn cache[i]\n\t\t\tcache[i] = 1\n\t\t\tfor neigh in g[i]:\n\t\t\t\tcache[i] = max(cache[i], 1 + dfs(neigh))\n\t\t\treturn cache[i]\n\t\tg = defaultdict(set)\n\t\tfor i in range(len(arr)):\n\t\t\tfor x in range(1, d + 1):\n\t\t\t\tif i - x >= 0 and arr[i - x] < arr[i]:\n\t\t\t\t\tg[i].add(i - x)\n\t\t\t\telse:\n\t\t\t\t\tbreak\n\t\t\tfor x in range(1, d + 1):\n\t\t\t\tif i + x < len(arr) and arr[i + x] < arr[i]:\n\t\t\t\t\tg[i].add(i + x)\n\t\t\t\telse:\n\t\t\t\t\tbreak\n\t\tcache = {}\n\t\tfor i in range(len(arr)):\n\t\t\tdfs(i)\n\t\treturn max(cache.values())\n", "class Solution:\n\n\tdef helper(self, idx):\n\t\tif self.dp[idx] != float('inf'):\n\t\t\treturn self.dp[idx]\n\t\tmax_step = 1\n\t\tfor c in range(idx - 1, max(0, idx - self.d) - 1, -1):\n\t\t\tif self.arr[idx] <= self.arr[c]:\n\t\t\t\tbreak\n\t\t\tmax_step = max(self.helper(c) + 1, max_step)\n\t\tfor c in range(idx + 1, min(self.n, idx + self.d + 1)):\n\t\t\tif self.arr[idx] <= self.arr[c]:\n\t\t\t\tbreak\n\t\t\tmax_step = max(self.helper(c) + 1, max_step)\n\t\tself.dp[idx] = max_step\n\t\treturn max_step\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\t\tself.n = len(arr)\n\t\tself.d = d\n\t\tself.arr = arr\n\t\tself.dp = [float('inf')] * self.n\n\t\tself.trans = defaultdict(list)\n\t\tmax_ = 0\n\t\tfor i in range(self.n):\n\t\t\tmax_ = max(self.helper(i), max_)\n\t\treturn max_\n", "class Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\t\tn = len(arr)\n\t\tgraph = collections.defaultdict(list)\n\t\tst = []\n\t\tfor i in range(n):\n\t\t\twhile st and arr[st[-1]] < arr[i]:\n\t\t\t\tj = st.pop()\n\t\t\t\tif i - j <= d:\n\t\t\t\t\tgraph[j].append(i)\n\t\t\tst.append(i)\n\t\tst = []\n\t\tfor i in range(n - 1, -1, -1):\n\t\t\twhile st and arr[st[-1]] < arr[i]:\n\t\t\t\tj = st.pop()\n\t\t\t\tif j - i <= d:\n\t\t\t\t\tgraph[j].append(i)\n\t\t\tst.append(i)\n\t\tvisited = {}\n\n\t\tdef dfs(i):\n\t\t\tif i in visited:\n\t\t\t\treturn visited[i]\n\t\t\tstep = 1\n\t\t\tfor j in graph[i]:\n\t\t\t\tstep = max(step, 1 + dfs(j))\n\t\t\tvisited[i] = step\n\t\t\treturn step\n\t\tres = 0\n\t\tfor i in range(n):\n\t\t\tres = max(res, dfs(i))\n\t\treturn res\n", "class Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\n\t\tdef helper(arr, index, d, memo):\n\t\t\tif arr[index] < 0 or not 0 <= index < len(arr):\n\t\t\t\treturn 0\n\t\t\tif index in memo:\n\t\t\t\treturn memo[index]\n\t\t\tleft_visited = 0\n\t\t\tright_visited = 0\n\t\t\tarr[index] = -arr[index]\n\t\t\tfor i in range(index + 1, index + d + 1):\n\t\t\t\tif i >= len(arr):\n\t\t\t\t\tbreak\n\t\t\t\tif abs(arr[i]) >= abs(arr[index]):\n\t\t\t\t\tbreak\n\t\t\t\tif arr[i] < 0:\n\t\t\t\t\tcontinue\n\t\t\t\tleft_visited = max(left_visited, helper(arr, i, d, memo))\n\t\t\tfor j in range(index - 1, index - d - 1, -1):\n\t\t\t\tif j < 0:\n\t\t\t\t\tbreak\n\t\t\t\tif abs(arr[j]) >= abs(arr[index]):\n\t\t\t\t\tbreak\n\t\t\t\tif arr[j] < 0:\n\t\t\t\t\tcontinue\n\t\t\t\tright_visited = max(right_visited, helper(arr, j, d, memo))\n\t\t\tarr[index] = -arr[index]\n\t\t\tmemo[index] = 1 + max(left_visited, right_visited)\n\t\t\treturn memo[index]\n\t\tmax_visited = 1\n\t\tp = False\n\t\tmemo = {}\n\t\tfor index in range(len(arr)):\n\t\t\tvisited = helper(arr, index, d, memo)\n\t\t\tmax_visited = max(visited, max_visited)\n\t\treturn max_visited\n", "class Solution:\n\tfrom collections import deque\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\t\tq = deque()\n\t\tn = len(arr)\n\t\tdp = [-1] * n\n\n\t\tdef solve(node):\n\t\t\tif node < 0 or node >= n:\n\t\t\t\treturn -1\n\t\t\tif dp[node] != -1:\n\t\t\t\treturn dp[node]\n\t\t\tans = 0\n\t\t\tfor i in range(1, d + 1):\n\t\t\t\tif node + i >= n or arr[node + i] >= arr[node]:\n\t\t\t\t\tbreak\n\t\t\t\tans = max(ans, solve(i + node))\n\t\t\tfor i in range(1, d + 1):\n\t\t\t\tif node - i < 0 or arr[node - i] >= arr[node]:\n\t\t\t\t\tbreak\n\t\t\t\tans = max(ans, solve(node - i))\n\t\t\tdp[node] = 1 + ans\n\t\t\treturn dp[node]\n\t\tfor i in range(n):\n\t\t\tsolve(i)\n\t\treturn max(dp)\n", "class Solution:\n\n\tdef maxJumps(self, lst: List[int], d: int) -> int:\n\n\t\tdef Ab(i, d, X):\n\t\t\tif i < 0 or i >= len(lst):\n\t\t\t\treturn -1\n\t\t\tif X <= lst[i]:\n\t\t\t\treturn None\n\t\t\tif dp[i] != -1:\n\t\t\t\treturn dp[i]\n\t\t\tm = 1\n\t\t\tfor j in range(1, d + 1):\n\t\t\t\ta = 0\n\t\t\t\ta = Ab(i - j, d, lst[i])\n\t\t\t\tif a == None:\n\t\t\t\t\tbreak\n\t\t\t\tm = max(m, 1 + a)\n\t\t\tfor j in range(1, d + 1):\n\t\t\t\tb = 0\n\t\t\t\tb = Ab(i + j, d, lst[i])\n\t\t\t\tif b == None:\n\t\t\t\t\tbreak\n\t\t\t\tm = max(m, 1 + b)\n\t\t\tdp[i] = m\n\t\t\treturn dp[i]\n\t\tdp = [-1 for i in lst]\n\t\tfor i in range(len(lst) - 1, -1, -1):\n\t\t\tAb(i, d, sys.maxsize)\n\t\treturn max(dp)\n", "class Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\t\tans = [1] * len(arr)\n\n\t\tdef dp(i):\n\t\t\tnonlocal ans, arr, d\n\t\t\tif ans[i] != 1:\n\t\t\t\treturn ans[i]\n\t\t\tfor dr in [-1, 1]:\n\t\t\t\tfor k in range(i, i + d * dr + dr, dr):\n\t\t\t\t\tif k < 0 or k == i:\n\t\t\t\t\t\tcontinue\n\t\t\t\t\tif k > len(arr) - 1 or arr[k] >= arr[i]:\n\t\t\t\t\t\tbreak\n\t\t\t\t\tans[i] = max(ans[i], 1 + dp(k))\n\t\t\treturn ans[i]\n\t\tfor i in range(len(arr)):\n\t\t\tdp(i)\n\t\treturn max(ans)\n", "class Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\t\tmem = [0] * len(arr)\n\n\t\tdef dfs(i):\n\t\t\tif mem[i]:\n\t\t\t\treturn mem[i]\n\t\t\tnum = 1\n\t\t\tj = i + 1\n\t\t\twhile j in range(i + 1, min(len(arr), i + d + 1)) and arr[j] < arr[i]:\n\t\t\t\tnum = max(num, dfs(j) + 1)\n\t\t\t\tj += 1\n\t\t\tj = i - 1\n\t\t\twhile j in range(max(0, i - d), i) and arr[j] < arr[i]:\n\t\t\t\tnum = max(num, dfs(j) + 1)\n\t\t\t\tj -= 1\n\t\t\tmem[i] = num\n\t\t\treturn mem[i]\n\t\tres = 0\n\t\tfor i in range(len(arr)):\n\t\t\tdfs(i)\n\t\t\tres = max(res, dfs(i) + 1)\n\t\treturn max(mem)\n", "import collections\n\nclass Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\t\toutEdges = {}\n\t\tinEdges = {}\n\t\tfor (idx, height) in enumerate(arr):\n\t\t\tjumpRangeRight = list(range(idx + 1, min(len(arr), idx + d + 1)))\n\t\t\tjumpRangeLeft = list(range(idx - 1, max(0, idx - d) - 1, -1))\n\t\t\tfor jumpRange in [jumpRangeLeft, jumpRangeRight]:\n\t\t\t\tfor jumpIdx in jumpRange:\n\t\t\t\t\tif arr[jumpIdx] >= arr[idx]:\n\t\t\t\t\t\tbreak\n\t\t\t\t\tif idx not in outEdges:\n\t\t\t\t\t\toutEdges[idx] = set()\n\t\t\t\t\toutEdges[idx].add(jumpIdx)\n\t\t\t\t\tif jumpIdx not in inEdges:\n\t\t\t\t\t\tinEdges[jumpIdx] = set()\n\t\t\t\t\tinEdges[jumpIdx].add(idx)\n\t\tnoInEdges = collections.deque()\n\t\tfor idx in range(len(arr)):\n\t\t\tif idx not in inEdges:\n\t\t\t\tnoInEdges.append(idx)\n\t\ttopologicalOrder = collections.deque()\n\t\twhile noInEdges:\n\t\t\tidx = noInEdges.pop()\n\t\t\ttopologicalOrder.append(idx)\n\t\t\tif idx not in outEdges:\n\t\t\t\tcontinue\n\t\t\tfor jumpIdx in outEdges[idx]:\n\t\t\t\tinEdges[jumpIdx].remove(idx)\n\t\t\t\tif not inEdges[jumpIdx]:\n\t\t\t\t\tnoInEdges.append(jumpIdx)\n\t\tmaxJumps = 1\n\t\tjumpCount = [1] * len(arr)\n\t\tfor idx in topologicalOrder:\n\t\t\tif idx not in outEdges:\n\t\t\t\tcontinue\n\t\t\tfor jumpIdx in outEdges[idx]:\n\t\t\t\tjumpCount[jumpIdx] = max(jumpCount[idx] + 1, jumpCount[jumpIdx])\n\t\t\t\tmaxJumps = max(jumpCount[jumpIdx], maxJumps)\n\t\treturn maxJumps\n\n\tdef maxJumpsBfs(self, arr: List[int], d: int) -> int:\n\t\tbfs = collections.deque()\n\t\tfor idx in range(len(arr)):\n\t\t\tbfs.append((idx, 1))\n\t\tstepCount = {}\n\t\tmaxSteps = 0\n\t\twhile bfs:\n\t\t\t(idx, steps) = bfs.popleft()\n\t\t\tif idx in stepCount and steps <= stepCount[idx]:\n\t\t\t\tcontinue\n\t\t\tstepCount[idx] = steps\n\t\t\tmaxSteps = max(steps, maxSteps)\n\t\t\tfor jumpIdx in range(idx + 1, min(len(arr), idx + d + 1)):\n\t\t\t\tif arr[jumpIdx] >= arr[idx]:\n\t\t\t\t\tbreak\n\t\t\t\tbfs.append((jumpIdx, steps + 1))\n\t\t\tfor jumpIdx in range(idx - 1, max(0, idx - d) - 1, -1):\n\t\t\t\tif arr[jumpIdx] >= arr[idx]:\n\t\t\t\t\tbreak\n\t\t\t\tbfs.append((jumpIdx, steps + 1))\n\t\treturn maxSteps\n", "class Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\t\tresult = 1\n\t\tN = len(arr)\n\t\tcache = {}\n\n\t\tdef helper(i: int) -> int:\n\t\t\tif i in cache:\n\t\t\t\treturn cache[i]\n\t\t\tresult = 1\n\t\t\tif (i == 0 or arr[i] <= arr[i - 1]) and (i == N - 1 or arr[i] <= arr[i + 1]):\n\t\t\t\tcache[i] = result\n\t\t\t\treturn cache[i]\n\t\t\tj = i - 1\n\t\t\twhile j >= 0 and j >= i - d and (arr[j] < arr[i]):\n\t\t\t\tcur = helper(j)\n\t\t\t\tresult = max(result, cur + 1)\n\t\t\t\tj = j - 1\n\t\t\tj = i + 1\n\t\t\twhile j < N and j <= i + d and (arr[j] < arr[i]):\n\t\t\t\tcur = helper(j)\n\t\t\t\tresult = max(result, cur + 1)\n\t\t\t\tj = j + 1\n\t\t\tcache[i] = result\n\t\t\treturn cache[i]\n\t\tfor i in range(N):\n\t\t\tcur = helper(i)\n\t\t\tresult = max(cur, result)\n\t\treturn result\n", "class Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\n\t\tdef find_longest_l(pos, d):\n\t\t\tif pos - 1 < 0 or arr[pos - 1] > arr[pos]:\n\t\t\t\treturn pos\n\t\t\ti = pos\n\t\t\twhile i > 0 and abs(pos - i) < d and (arr[i - 1] < arr[pos]):\n\t\t\t\ti -= 1\n\t\t\treturn i\n\n\t\tdef find_longest_r(pos, d):\n\t\t\tif pos + 1 >= len(arr) or arr[pos + 1] > arr[pos]:\n\t\t\t\treturn pos\n\t\t\ti = pos\n\t\t\twhile i < len(arr) - 1 and abs(pos - i) < d and (arr[i + 1] < arr[pos]):\n\t\t\t\ti += 1\n\t\t\treturn i\n\n\t\tdef jump(pos, number_of_locations, seen):\n\t\t\tmaximum_locations = number_of_locations\n\t\t\tL = find_longest_l(pos, d)\n\t\t\tR = find_longest_r(pos, d)\n\t\t\tfor i in range(L, R + 1):\n\t\t\t\tif i == pos:\n\t\t\t\t\tcontinue\n\t\t\t\tif i not in seen:\n\t\t\t\t\tjumps_to_i = jump(i, number_of_locations, seen)\n\t\t\t\t\tmaximum_locations = max(maximum_locations, jumps_to_i + 1)\n\t\t\t\telse:\n\t\t\t\t\tjumps_to_i = seen[i]\n\t\t\t\t\tmaximum_locations = max(maximum_locations, jumps_to_i + 1)\n\t\t\tseen[pos] = maximum_locations\n\t\t\treturn maximum_locations\n\t\tindices = [(i, arr[i]) for i in range(len(arr))]\n\t\tindices.sort(key=lambda x: x[1], reverse=True)\n\t\tseen = {}\n\t\treturn max((jump(x[0], 1, seen) for x in indices))\n", "class Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\t\tl = len(arr)\n\t\t(self.check, self.seen) = ([[] for _ in range(l)], dict())\n\t\tfor (i, v) in enumerate(arr):\n\t\t\tfor sign in (1, -1):\n\t\t\t\tfor x in range(sign, (d + 1) * sign, sign):\n\t\t\t\t\tif i + x not in list(range(l)) or v <= arr[i + x]:\n\t\t\t\t\t\tbreak\n\t\t\t\t\tself.check[i].append(i + x)\n\t\t\tif not self.check[i]:\n\t\t\t\tself.seen[i] = 1\n\t\treturn max((self.helper(i) for i in range(l)))\n\n\tdef helper(self, p):\n\t\tif p not in self.seen:\n\t\t\tres = 0\n\t\t\tfor n in self.check[p]:\n\t\t\t\tres = max(res, self.seen.get(n, self.helper(n)) + 1)\n\t\t\tself.seen[p] = res\n\t\treturn self.seen[p]\n", "class Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\t\tmax_pos = 1\n\t\tmemo = {}\n\n\t\tdef helper(i):\n\t\t\tif i in list(memo.keys()):\n\t\t\t\treturn memo[i]\n\t\t\tres = 0\n\t\t\tj = i - 1\n\t\t\twhile 0 <= j < len(arr) and i - j <= d and (arr[j] < arr[i]):\n\t\t\t\tres = max(res, helper(j))\n\t\t\t\tj -= 1\n\t\t\tj = i + 1\n\t\t\twhile 0 <= j < len(arr) and j - i <= d and (arr[j] < arr[i]):\n\t\t\t\tres = max(res, helper(j))\n\t\t\t\tj += 1\n\t\t\tres = res + 1\n\t\t\tmemo[i] = res\n\t\t\treturn res\n\t\tfor i in range(len(arr)):\n\t\t\tmax_pos = max(max_pos, helper(i))\n\t\treturn max_pos\n", "class Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\n\t\tdef backtracking(idx):\n\t\t\tnonlocal memo, max_val\n\t\t\tif idx in memo:\n\t\t\t\treturn memo[idx]\n\t\t\tlstack = []\n\t\t\trstack = []\n\t\t\tlbarrier = False\n\t\t\trbarrier = False\n\t\t\tfor i in range(1, d + 1):\n\t\t\t\tif not lbarrier and idx - i >= 0 and (arr[idx - i] < arr[idx]):\n\t\t\t\t\tlstack.append(idx - i)\n\t\t\t\telse:\n\t\t\t\t\tlbarrier = True\n\t\t\t\tif not rbarrier and idx + i < len(arr) and (arr[idx + i] < arr[idx]):\n\t\t\t\t\trstack.append(idx + i)\n\t\t\t\telse:\n\t\t\t\t\trbarrier = True\n\t\t\tljump = 1\n\t\t\twhile lstack:\n\t\t\t\tlidx = lstack.pop()\n\t\t\t\tljump = max(ljump, 1 + backtracking(lidx))\n\t\t\trjump = 1\n\t\t\twhile rstack:\n\t\t\t\tridx = rstack.pop()\n\t\t\t\trjump = max(rjump, 1 + backtracking(ridx))\n\t\t\tjump = max(ljump, rjump)\n\t\t\tmemo[idx] = jump\n\t\t\tmax_val = max(max_val, jump)\n\t\t\treturn jump\n\t\tmemo = {}\n\t\tmax_val = 0\n\t\tfor i in range(len(arr)):\n\t\t\tbacktracking(i)\n\t\treturn max_val\n", "class Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\t\tjumps = defaultdict(list)\n\n\t\tdef check(it):\n\t\t\tstack = []\n\t\t\tfor i in it:\n\t\t\t\twhile stack and arr[stack[-1]] < arr[i]:\n\t\t\t\t\tj = stack.pop()\n\t\t\t\t\tif abs(i - j) <= d:\n\t\t\t\t\t\tjumps[j].append(i)\n\t\t\t\tstack.append(i)\n\t\tN = len(arr)\n\t\tcheck(range(N))\n\t\tcheck(reversed(range(N)))\n\n\t\t@lru_cache(None)\n\t\tdef dfs(i):\n\t\t\treturn 1 + max((dfs(j) for j in jumps[i]), default=0)\n\t\treturn max((dfs(i) for i in range(N)))\n", "class Solution:\n\n\tdef maxJumps(self, A: List[int], d: int) -> int:\n\t\tdp = [1] * len(A)\n\t\tsteps = [(v, i) for (i, v) in enumerate(A)]\n\t\tsteps.sort()\n\t\tfor (val, i) in steps:\n\t\t\tmaxVal = val\n\t\t\tfor j in range(i + 1, min(i + d + 1, len(steps))):\n\t\t\t\tif A[j] > maxVal:\n\t\t\t\t\tmaxVal = max(maxVal, A[j])\n\t\t\t\t\tdp[j] = max(dp[j], dp[i] + 1)\n\t\t\tmaxVal = val\n\t\t\tfor j in reversed(range(max(i - d, 0), i)):\n\t\t\t\tif A[j] > maxVal:\n\t\t\t\t\tmaxVal = max(maxVal, A[j])\n\t\t\t\t\tdp[j] = max(dp[j], dp[i] + 1)\n\t\treturn max(dp)\n", "class Solution:\n\n\tdef maxJumps(self, A: List[int], d: int) -> int:\n\t\tn = len(A)\n\t\tgraph = {}\n\t\tinorder = [0] * n\n\t\tfor i in range(n):\n\t\t\tgraph[i] = []\n\t\t\tis_greater = False\n\t\t\tcur_max = -1\n\t\t\tfor ind in range(i - 1, max(-1, i - d - 1), -1):\n\t\t\t\tif A[ind] >= A[i]:\n\t\t\t\t\tif A[ind] >= cur_max and A[ind] > A[i]:\n\t\t\t\t\t\tcur_max = A[ind]\n\t\t\t\t\t\tgraph[ind].append(i)\n\t\t\t\t\t\tinorder[i] += 1\n\t\t\t\t\tis_greater = True\n\t\t\t\telse:\n\t\t\t\t\tif is_greater:\n\t\t\t\t\t\tcontinue\n\t\t\t\t\tgraph[i].append(ind)\n\t\t\t\t\tinorder[ind] += 1\n\t\tstack = []\n\t\tdp = [1] * n\n\t\tfor i in range(n):\n\t\t\tif inorder[i] == 0:\n\t\t\t\tstack.append(i)\n\t\twhile stack:\n\t\t\ttop = stack.pop()\n\t\t\tfor value in graph[top]:\n\t\t\t\tinorder[value] -= 1\n\t\t\t\tdp[value] = max(dp[value], dp[top] + 1)\n\t\t\t\tif inorder[value] == 0:\n\t\t\t\t\tstack.append(value)\n\t\treturn max(dp)\n", "class Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\t\tbook = [1] * len(arr)\n\t\tindex = collections.defaultdict(list)\n\t\tfor i in range(len(arr)):\n\t\t\tindex[arr[i]].append(i)\n\t\tval = list(index.keys())\n\t\tval.sort(reverse=True)\n\t\tfor v in val:\n\t\t\tfor i in index[v]:\n\t\t\t\theight = arr[i]\n\t\t\t\tfor j in range(i + 1, i + d + 1):\n\t\t\t\t\tif j == len(arr):\n\t\t\t\t\t\tbreak\n\t\t\t\t\tif arr[j] > height:\n\t\t\t\t\t\tbook[i] = max(book[i], book[j] + 1)\n\t\t\t\t\t\theight = arr[j]\n\t\t\t\theight = arr[i]\n\t\t\t\tfor j in range(i - 1, i - d - 1, -1):\n\t\t\t\t\tif j == -1:\n\t\t\t\t\t\tbreak\n\t\t\t\t\tif arr[j] > height:\n\t\t\t\t\t\tbook[i] = max(book[i], book[j] + 1)\n\t\t\t\t\t\theight = arr[j]\n\t\treturn max(book)\n", "class Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\t\t(n, inf) = (len(arr), float('inf'))\n\t\t(a, s) = ([[] for _ in range(n)], [(inf, -1)])\n\t\tfor (i, x) in enumerate(arr):\n\t\t\twhile s[-1][0] < x:\n\t\t\t\tif s[-1][1] >= i - d:\n\t\t\t\t\ta[i].append(s[-1][1])\n\t\t\t\ts.pop()\n\t\t\ts.append((x, i))\n\t\ts = [(inf, -1)]\n\t\tfor (i, x) in reversed(list(enumerate(arr))):\n\t\t\twhile s[-1][0] < x:\n\t\t\t\tif s[-1][1] <= i + d:\n\t\t\t\t\ta[i].append(s[-1][1])\n\t\t\t\ts.pop()\n\t\t\ts.append((x, i))\n\t\t(dp, v) = ([1] * n, [0] * n)\n\n\t\tdef dfs(i):\n\t\t\tif v[i]:\n\t\t\t\treturn\n\t\t\tv[i] = 1\n\t\t\tfor j in a[i]:\n\t\t\t\tdfs(j)\n\t\t\t\tdp[i] = max(dp[i], dp[j] + 1)\n\t\tfor i in range(n):\n\t\t\tdfs(i)\n\t\treturn max(dp)\n", "class Solution:\n\n\tdef maxJumps(self, A: List[int], d: int) -> int:\n\t\tN = len(A)\n\t\tjumpable = collections.defaultdict(list)\n\n\t\tdef find_jumpable_indices(iter):\n\t\t\tstack = []\n\t\t\tfor i in iter:\n\t\t\t\twhile stack and A[stack[-1]] < A[i]:\n\t\t\t\t\tj = stack.pop()\n\t\t\t\t\tif abs(i - j) <= d:\n\t\t\t\t\t\tjumpable[i].append(j)\n\t\t\t\tstack.append(i)\n\t\tfind_jumpable_indices(list(range(N)))\n\t\tfind_jumpable_indices(reversed(list(range(N))))\n\t\tdp = [-1] * N\n\n\t\tdef dfs(idx):\n\t\t\tif dp[idx] > -1:\n\t\t\t\treturn dp[idx]\n\t\t\tres = 1\n\t\t\tfor j in jumpable[idx]:\n\t\t\t\tres = max(res, 1 + dfs(j))\n\t\t\tdp[idx] = res\n\t\t\treturn res\n\t\treturn max(list(map(dfs, list(range(N)))))\n", "from collections import *\nfrom functools import *\nimport numpy as np\nfrom typing import *\n\nclass Solution:\n\n\tdef maxJumps(self, nums: List[int], d: int) -> int:\n\t\tN = len(nums)\n\t\tleft_jumps = [[] for _ in range(N)]\n\t\tleft = [(-1, np.inf)]\n\t\tfor i in range(N):\n\t\t\twhile left[-1][1] < nums[i]:\n\t\t\t\t(j, _) = left.pop()\n\t\t\t\tif abs(j - i) <= d:\n\t\t\t\t\tleft_jumps[i].append(j)\n\t\t\tleft.append((i, nums[i]))\n\t\tright_jumps = [[] for _ in range(N)]\n\t\tright = [(-1, np.inf)]\n\t\tfor i in reversed(range(N)):\n\t\t\twhile right[-1][1] < nums[i]:\n\t\t\t\t(j, _) = right.pop()\n\t\t\t\tif abs(j - i) <= d:\n\t\t\t\t\tright_jumps[i].append(j)\n\t\t\tright.append((i, nums[i]))\n\n\t\t@lru_cache(maxsize=None)\n\t\tdef longest_path_from(pos: int):\n\t\t\tleft_max = max((longest_path_from(p) for p in left_jumps[pos]), default=0)\n\t\t\tright_max = max((longest_path_from(p) for p in right_jumps[pos]), default=0)\n\t\t\treturn max(1 + left_max, 1 + right_max)\n\t\treturn max((longest_path_from(i) for i in range(N)))\n", "class Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\t\tA = arr\n\t\tn = len(A)\n\n\t\t@lru_cache(None)\n\t\tdef dp(i):\n\t\t\tcount = 0\n\t\t\tfor j in range(i - 1, i - d - 1, -1):\n\t\t\t\tif j >= 0 and A[j] < A[i]:\n\t\t\t\t\tcount = max(count, dp(j))\n\t\t\t\telse:\n\t\t\t\t\tbreak\n\t\t\tfor j in range(i + 1, i + d + 1):\n\t\t\t\tif j < n and A[j] < A[i]:\n\t\t\t\t\tcount = max(count, dp(j))\n\t\t\t\telse:\n\t\t\t\t\tbreak\n\t\t\treturn count + 1\n\t\tres = 0\n\t\tfor k in range(n):\n\t\t\tres = max(res, dp(k))\n\t\treturn res\n", "class Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\t\tn = len(arr)\n\t\tdp = [1 for i in range(n)]\n\t\tp = []\n\t\tfor (idx, x) in enumerate(arr):\n\t\t\tp.append((x, idx))\n\t\tp.sort(reverse=True)\n\t\tfor i in range(n):\n\t\t\tidx = p[i][1]\n\t\t\tfor j in range(idx + 1, min(n, d + idx + 1)):\n\t\t\t\tif arr[j] >= arr[idx]:\n\t\t\t\t\tbreak\n\t\t\t\tdp[j] = max(dp[j], dp[idx] + 1)\n\t\t\tfor j in range(idx - 1, max(-1, idx - d - 1), -1):\n\t\t\t\tif arr[j] >= arr[idx]:\n\t\t\t\t\tbreak\n\t\t\t\tdp[j] = max(dp[j], dp[idx] + 1)\n\t\treturn max([dp[i] for i in range(n)])\n", "from functools import lru_cache\n\nclass Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\t\tlim = len(arr)\n\n\t\t@lru_cache(None)\n\t\tdef r(i):\n\t\t\ttmp = [0]\n\t\t\tfor j in range(i - 1, i - d - 1, -1):\n\t\t\t\tif j < 0:\n\t\t\t\t\tbreak\n\t\t\t\tif arr[j] < arr[i]:\n\t\t\t\t\ttmp.append(1 + r(j))\n\t\t\t\telse:\n\t\t\t\t\tbreak\n\t\t\tfor j in range(i + 1, i + d + 1):\n\t\t\t\tif j >= lim:\n\t\t\t\t\tbreak\n\t\t\t\tif arr[j] < arr[i]:\n\t\t\t\t\ttmp.append(1 + r(j))\n\t\t\t\telse:\n\t\t\t\t\tbreak\n\t\t\treturn max(tmp)\n\t\tmx = 0\n\t\tfor i in range(0, lim):\n\t\t\tval = 1 + r(i)\n\t\t\tif val > mx:\n\t\t\t\tmx = val\n\t\treturn mx\n", "class Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\n\t\t@lru_cache(None)\n\t\tdef jump(mid):\n\t\t\tleft = max(mid - d, 0)\n\t\t\tright = min(mid + d, len(arr) - 1)\n\t\t\tres = 1\n\t\t\tfor i in range(mid - 1, left - 1, -1):\n\t\t\t\tif arr[i] >= arr[mid]:\n\t\t\t\t\tbreak\n\t\t\t\tres = max(res, jump(i) + 1)\n\t\t\tfor i in range(mid + 1, right + 1):\n\t\t\t\tif arr[i] >= arr[mid]:\n\t\t\t\t\tbreak\n\t\t\t\tres = max(res, jump(i) + 1)\n\t\t\treturn res\n\t\tres = [1] * len(arr)\n\t\tfor i in range(len(arr)):\n\t\t\tres[i] = jump(i)\n\t\treturn max(res)\n", "import functools\n\nclass Solution:\n\n\tdef maxJumps(self, arr, d: int) -> int:\n\n\t\t@functools.lru_cache(None)\n\t\tdef helper(i):\n\t\t\tans = 1\n\t\t\tfor index in range(i + 1, min(len(arr), i + d + 1)):\n\t\t\t\tif arr[i] > arr[index]:\n\t\t\t\t\tans = max(ans, 1 + helper(index))\n\t\t\t\telse:\n\t\t\t\t\tbreak\n\t\t\tfor index in range(i - 1, max(-1, i - d - 1), -1):\n\t\t\t\tif arr[i] > arr[index]:\n\t\t\t\t\tans = max(ans, 1 + helper(index))\n\t\t\t\telse:\n\t\t\t\t\tbreak\n\t\t\treturn ans\n\t\tmaxJumps = 1\n\t\tfor i in range(len(arr)):\n\t\t\tmaxJumps = max(maxJumps, helper(i))\n\t\treturn maxJumps\n", "class Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\t\tl = []\n\t\tn = len(arr)\n\t\tfor i in range(n):\n\t\t\tl.append([arr[i], i])\n\t\tl.sort()\n\t\tl = [i[1] for i in l]\n\t\tdp = [1] * n\n\t\tfor i in l:\n\t\t\tfor j in range(i + 1, min(n, i + d + 1)):\n\t\t\t\tif arr[i] > arr[j]:\n\t\t\t\t\tdp[i] = max(dp[i], dp[j] + 1)\n\t\t\t\telse:\n\t\t\t\t\tbreak\n\t\t\tfor j in range(i - 1, max(-1, i - d - 1), -1):\n\t\t\t\tif arr[i] > arr[j]:\n\t\t\t\t\tdp[i] = max(dp[i], dp[j] + 1)\n\t\t\t\telse:\n\t\t\t\t\tbreak\n\t\treturn max(dp)\n", "import functools\n\nclass Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\n\t\t@functools.lru_cache(None)\n\t\tdef check_i(inow):\n\t\t\tmax_son = 0\n\t\t\tfor i in range(1, min(d + 1, len(arr) - inow)):\n\t\t\t\tif arr[inow + i] >= arr[inow]:\n\t\t\t\t\tbreak\n\t\t\t\tmax_son = max(max_son, check_i(inow + i))\n\t\t\tfor i in range(1, min(d + 1, inow + 1)):\n\t\t\t\tif arr[inow - i] >= arr[inow]:\n\t\t\t\t\tbreak\n\t\t\t\tmax_son = max(max_son, check_i(inow - i))\n\t\t\treturn max_son + 1\n\t\treturn max([check_i(i) for i in range(len(arr))])\n", "class Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\t\tn = len(arr)\n\t\tdp = [1] * n\n\t\tfor (a, i) in sorted(([a, i] for (i, a) in enumerate(arr))):\n\t\t\tfor di in [-1, 1]:\n\t\t\t\tfor j in range(i + di, i + d * di + di, di):\n\t\t\t\t\tif not (0 <= j < n and arr[j] < arr[i]):\n\t\t\t\t\t\tbreak\n\t\t\t\t\tdp[i] = max(dp[i], dp[j] + 1)\n\t\treturn max(dp)\n", "class Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\t\tN = len(arr)\n\n\t\t@lru_cache(None)\n\t\tdef rec(idx):\n\t\t\tif not 0 <= idx < N:\n\t\t\t\treturn -inf\n\t\t\tans = 1\n\t\t\tfor i in range(idx - 1, idx - d - 1, -1):\n\t\t\t\tif i < 0 or arr[i] >= arr[idx]:\n\t\t\t\t\tbreak\n\t\t\t\tans = max(ans, rec(i) + 1)\n\t\t\tfor i in range(idx + 1, idx + d + 1):\n\t\t\t\tif i >= N or arr[i] >= arr[idx]:\n\t\t\t\t\tbreak\n\t\t\t\tans = max(ans, rec(i) + 1)\n\t\t\treturn ans\n\t\tans = 0\n\t\tfor i in range(N):\n\t\t\tans = max(ans, rec(i))\n\t\treturn ans\n", "class Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\n\t\t@lru_cache(None)\n\t\tdef dfs(i):\n\t\t\tif i == 0 and i + 1 < len(arr):\n\t\t\t\tif arr[i] <= arr[i + 1]:\n\t\t\t\t\treturn 1\n\t\t\telif i == len(arr) - 1 and i - 1 >= 0:\n\t\t\t\tif arr[i] <= arr[i - 1]:\n\t\t\t\t\treturn 1\n\t\t\telif i - 1 >= 0 and i + 1 < len(arr) and (arr[i] <= arr[i - 1]) and (arr[i] <= arr[i + 1]):\n\t\t\t\treturn 1\n\t\t\tleft_step = 1\n\t\t\tfor j in range(i + 1, i + d + 1):\n\t\t\t\tif j >= len(arr) or arr[j] >= arr[i]:\n\t\t\t\t\tbreak\n\t\t\t\tleft_step = max(left_step, 1 + dfs(j))\n\t\t\tright_step = 1\n\t\t\tfor j in range(i - 1, i - d - 1, -1):\n\t\t\t\tif j < 0 or arr[j] >= arr[i]:\n\t\t\t\t\tbreak\n\t\t\t\tright_step = max(right_step, 1 + dfs(j))\n\t\t\treturn max(left_step, right_step)\n\t\tmax_step = 0\n\t\tfor i in range(len(arr)):\n\t\t\tmax_step = max(max_step, dfs(i))\n\t\treturn max_step\n", "class Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\t\tfrom functools import lru_cache\n\t\tn = len(arr)\n\n\t\t@lru_cache(maxsize=None)\n\t\tdef f(i):\n\t\t\tres = 1\n\t\t\tfor j in range(i + 1, min(i + d + 1, n)):\n\t\t\t\tif arr[j] < arr[i]:\n\t\t\t\t\tres = max(res, 1 + f(j))\n\t\t\t\telse:\n\t\t\t\t\tbreak\n\t\t\tfor j in range(i - 1, max(-1, i - d - 1), -1):\n\t\t\t\tif arr[j] < arr[i]:\n\t\t\t\t\tres = max(res, 1 + f(j))\n\t\t\t\telse:\n\t\t\t\t\tbreak\n\t\t\treturn res\n\t\treturn max((f(_) for _ in range(n)))\n", "class Solution:\n\n\tdef maxJumps(self, A: List[int], d: int) -> int:\n\t\tn = len(A)\n\n\t\t@lru_cache(None)\n\t\tdef helper(i):\n\t\t\tans = 1\n\t\t\tl = max(0, i - d)\n\t\t\tr = min(n - 1, i + d)\n\t\t\tfor j in reversed(range(l, i)):\n\t\t\t\tif A[j] < A[i]:\n\t\t\t\t\tans = max(ans, 1 + helper(j))\n\t\t\t\telse:\n\t\t\t\t\tbreak\n\t\t\tfor j in range(i + 1, r + 1):\n\t\t\t\tif A[j] < A[i]:\n\t\t\t\t\tans = max(ans, 1 + helper(j))\n\t\t\t\telse:\n\t\t\t\t\tbreak\n\t\t\treturn ans\n\t\tans = max([helper(i) for i in range(n)])\n\t\treturn ans\n", "class Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\t\tsorted_indexes = sorted(range(len(arr)), key=lambda i: arr[i])\n\t\tn = len(arr)\n\t\tdp = [1] * n\n\n\t\tdef get_neighs(cur):\n\t\t\tneighs = []\n\t\t\tfor i in range(cur + 1, min(cur + d + 1, n)):\n\t\t\t\tif arr[i] < arr[cur]:\n\t\t\t\t\tneighs.append(i)\n\t\t\t\telse:\n\t\t\t\t\tbreak\n\t\t\tfor i in range(cur - 1, max(cur - d - 1, -1), -1):\n\t\t\t\tif arr[i] < arr[cur]:\n\t\t\t\t\tneighs.append(i)\n\t\t\t\telse:\n\t\t\t\t\tbreak\n\t\t\treturn neighs\n\t\tfor cur in sorted_indexes:\n\t\t\tneighs = get_neighs(cur)\n\t\t\tfor neigh in neighs:\n\t\t\t\tdp[cur] = max(dp[cur], dp[neigh] + 1)\n\t\treturn max(dp)\n", "class Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\t\thp = [(v, i) for (i, v) in enumerate(arr)]\n\t\theapq.heapify(hp)\n\t\tdp = [0] * len(arr)\n\t\tres = 0\n\t\twhile hp:\n\t\t\t(h, i) = heapq.heappop(hp)\n\t\t\ttmp = 1\n\t\t\tfor j in range(i - 1, i - 1 - d, -1):\n\t\t\t\tif j < 0 or arr[j] >= arr[i]:\n\t\t\t\t\tbreak\n\t\t\t\ttmp = max(tmp, dp[j] + 1)\n\t\t\tfor j in range(i + 1, i + 1 + d):\n\t\t\t\tif j >= len(arr) or arr[j] >= arr[i]:\n\t\t\t\t\tbreak\n\t\t\t\ttmp = max(tmp, dp[j] + 1)\n\t\t\tdp[i] = tmp\n\t\treturn max(dp)\n", "class Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\t\tdp = [1] * len(arr)\n\t\ta = []\n\t\tfor (idx, val) in enumerate(arr):\n\t\t\ta.append((val, idx))\n\t\ta.sort()\n\t\tprint(a)\n\t\tfor (_, idx) in a:\n\t\t\tfor i in range(1, d + 1):\n\t\t\t\tif idx + i < len(arr) and arr[idx + i] < arr[idx]:\n\t\t\t\t\tdp[idx] = max(dp[idx], dp[idx + i] + 1)\n\t\t\t\telse:\n\t\t\t\t\tbreak\n\t\t\tfor i in range(1, d + 1):\n\t\t\t\tif 0 <= idx - i and arr[idx - i] < arr[idx]:\n\t\t\t\t\tdp[idx] = max(dp[idx], dp[idx - i] + 1)\n\t\t\t\telse:\n\t\t\t\t\tbreak\n\t\treturn max(dp)\n", "class Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\t\tdp = [0] * len(arr)\n\t\tpath = {i: [(i, arr[i])] for i in range(len(arr))}\n\n\t\tdef jump(i):\n\t\t\tnonlocal dp, path\n\t\t\tif dp[i] != 0:\n\t\t\t\treturn dp[i]\n\t\t\t(left, right) = (0, 0)\n\t\t\t(nl, nr) = (i, i)\n\t\t\tfor j in range(i + 1, i + d + 1):\n\t\t\t\tif j >= len(arr):\n\t\t\t\t\tbreak\n\t\t\t\tif arr[j] < arr[i]:\n\t\t\t\t\tt = jump(j)\n\t\t\t\t\tif right < t:\n\t\t\t\t\t\tright = t\n\t\t\t\t\t\tnr = j\n\t\t\t\telse:\n\t\t\t\t\tbreak\n\t\t\tfor j in range(i - 1, i - d - 1, -1):\n\t\t\t\tif j < 0:\n\t\t\t\t\tbreak\n\t\t\t\tif arr[j] < arr[i]:\n\t\t\t\t\tt = jump(j)\n\t\t\t\t\tif left < t:\n\t\t\t\t\t\tleft = t\n\t\t\t\t\t\tnl = j\n\t\t\t\telse:\n\t\t\t\t\tbreak\n\t\t\tif left < right and right > 0:\n\t\t\t\tpath[i] += path[nr]\n\t\t\telif left >= right and left > 0:\n\t\t\t\tpath[i] += path[nl]\n\t\t\tdp[i] = max(left, right) + 1\n\t\t\treturn dp[i]\n\t\tans = 0\n\t\tfor i in range(len(arr)):\n\t\t\tjump(i)\n\t\t\tans = max(ans, dp[i])\n\t\treturn ans\n", "import functools\n\nclass Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\n\t\t@functools.lru_cache(None)\n\t\tdef jump(index):\n\t\t\tres = 0\n\t\t\tfor direction in [-1, 1]:\n\t\t\t\tfor x in range(1, d + 1):\n\t\t\t\t\tj = index + x * direction\n\t\t\t\t\tif 0 <= j < len(arr) and arr[j] < arr[index]:\n\t\t\t\t\t\tres = max(res, jump(j))\n\t\t\t\t\telse:\n\t\t\t\t\t\tbreak\n\t\t\treturn res + 1\n\t\treturn max((jump(index) for index in range(len(arr))))\n", "class Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\t\tN = len(arr)\n\t\tdp = [None] * N\n\n\t\tdef cdp(i):\n\t\t\tif dp[i] != None:\n\t\t\t\treturn dp[i]\n\t\t\tdp[i] = 1\n\t\t\tfor j in range(i - 1, max(0, i - d) - 1, -1):\n\t\t\t\tif arr[j] >= arr[i]:\n\t\t\t\t\tbreak\n\t\t\t\tdp[i] = max(dp[i], 1 + cdp(j))\n\t\t\tfor j in range(i + 1, min(N - 1, i + d) + 1):\n\t\t\t\tif arr[j] >= arr[i]:\n\t\t\t\t\tbreak\n\t\t\t\tdp[i] = max(dp[i], 1 + cdp(j))\n\t\t\treturn dp[i]\n\t\tfor i in range(N):\n\t\t\tcdp(i)\n\t\treturn max(dp)\n", "from functools import lru_cache\n\nclass Solution:\n\n\tdef maxJumps(self, arr, d):\n\t\tn = len(arr)\n\n\t\t@lru_cache(maxsize=None)\n\t\tdef findMaxReach(index):\n\t\t\tbest = 1\n\t\t\tfor i in range(1, d + 1):\n\t\t\t\tcurIndex = index - i\n\t\t\t\tif 0 <= curIndex < n and arr[curIndex] < arr[index]:\n\t\t\t\t\tbest = max(findMaxReach(curIndex) + 1, best)\n\t\t\t\telse:\n\t\t\t\t\tbreak\n\t\t\tfor i in range(1, d + 1):\n\t\t\t\tcurIndex = index + i\n\t\t\t\tif 0 <= curIndex < n and arr[curIndex] < arr[index]:\n\t\t\t\t\tbest = max(findMaxReach(curIndex) + 1, best)\n\t\t\t\telse:\n\t\t\t\t\tbreak\n\t\t\treturn best\n\t\tans = 0\n\t\tfor i in range(n):\n\t\t\tans = max(findMaxReach(i), ans)\n\t\treturn ans\n", "from functools import lru_cache\n\nclass Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\t\tn = len(arr)\n\n\t\t@lru_cache(maxsize=None)\n\t\tdef jump(i):\n\t\t\tres = 1\n\n\t\t\tdef visit(rng):\n\t\t\t\tnonlocal res\n\t\t\t\tfor j in rng:\n\t\t\t\t\tif not 0 <= j < n or arr[j] >= arr[i]:\n\t\t\t\t\t\tbreak\n\t\t\t\t\tres = max(res, 1 + jump(j))\n\t\t\tvisit(range(i - 1, i - d - 1, -1))\n\t\t\tvisit(range(i + 1, i + d + 1))\n\t\t\treturn res\n\t\treturn max([jump(i) for i in range(n)])\n", "class Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\t\tdp = [0 for i in range(len(arr))]\n\n\t\tdef findMaxJumps(i):\n\t\t\tif dp[i] != 0:\n\t\t\t\treturn dp[i]\n\t\t\telse:\n\t\t\t\tans = 1\n\t\t\t\tfor j in range(i + 1, min(i + d + 1, len(arr))):\n\t\t\t\t\tif arr[j] >= arr[i]:\n\t\t\t\t\t\tbreak\n\t\t\t\t\tans = max(ans, 1 + findMaxJumps(j))\n\t\t\t\tfor j in range(i - 1, max(i - d, 0) - 1, -1):\n\t\t\t\t\tif arr[j] >= arr[i]:\n\t\t\t\t\t\tbreak\n\t\t\t\t\tans = max(ans, 1 + findMaxJumps(j))\n\t\t\t\tdp[i] = ans\n\t\t\t\treturn ans\n\t\tans = 1\n\t\tfor i in range(len(arr)):\n\t\t\tans = max(ans, findMaxJumps(i))\n\t\treturn ans\n", "class Solution2:\n\n\tdef maxJumps(self, arr, d):\n\t\tn = len(arr)\n\t\tdp = [1] * n\n\t\tfor (a, i) in sorted(([a, i] for (i, a) in enumerate(arr))):\n\t\t\tfor di in [-1, 1]:\n\t\t\t\tfor j in range(i + di, i + di + d * di, di):\n\t\t\t\t\tif not (0 <= j < n and arr[j] < arr[i]):\n\t\t\t\t\t\tbreak\n\t\t\t\t\tdp[i] = max(dp[i], dp[j] + 1)\n\t\treturn max(dp)\n\nclass Solution:\n\n\tdef maxJumps(self, arr, d):\n\t\tn = len(arr)\n\t\tdp = [1] * (n + 1)\n\t\tstack = []\n\t\tfor (i, a) in enumerate(arr + [float('inf')]):\n\t\t\twhile stack and arr[stack[-1]] < a:\n\t\t\t\tL = [stack.pop()]\n\t\t\t\twhile stack and arr[stack[-1]] == arr[L[0]]:\n\t\t\t\t\tL.append(stack.pop())\n\t\t\t\tfor j in L:\n\t\t\t\t\tif i - j <= d:\n\t\t\t\t\t\tdp[i] = max(dp[i], dp[j] + 1)\n\t\t\t\t\tif stack and j - stack[-1] <= d:\n\t\t\t\t\t\tdp[stack[-1]] = max(dp[stack[-1]], dp[j] + 1)\n\t\t\tstack.append(i)\n\t\treturn max(dp[:-1])\n\nclass Solution1:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\t\tn = len(arr)\n\t\tres = [0] * n\n\n\t\tdef dp(i):\n\t\t\tif res[i]:\n\t\t\t\treturn res[i]\n\t\t\tres[i] = 1\n\t\t\tfor di in [-1, 1]:\n\t\t\t\tfor j in range(i + di, i + di + d * di, di):\n\t\t\t\t\tif not (0 <= j < n and arr[j] < arr[i]):\n\t\t\t\t\t\tbreak\n\t\t\t\t\tres[i] = max(res[i], dp(j) + 1)\n\t\t\treturn res[i]\n\t\treturn max(list(map(dp, list(range(n)))))\n", "class Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\t\tsorted_indexes = sorted(range(len(arr)), key=lambda i: arr[i])\n\t\tn = len(arr)\n\t\tdp = [1] * n\n\n\t\tdef get_neighs(cur):\n\t\t\tneighs = []\n\t\t\tdirections = [1, -1]\n\t\t\tfor dire in directions:\n\t\t\t\tfor i in range(cur + dire, cur + (d + 1) * dire, dire):\n\t\t\t\t\tif i < 0 or i >= n:\n\t\t\t\t\t\tbreak\n\t\t\t\t\tif arr[i] >= arr[cur]:\n\t\t\t\t\t\tbreak\n\t\t\t\t\tneighs.append(i)\n\t\t\treturn neighs\n\t\tfor cur in sorted_indexes:\n\t\t\tfor neigh in get_neighs(cur):\n\t\t\t\tdp[cur] = max(dp[cur], dp[neigh] + 1)\n\t\treturn max(dp)\n", "class Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\t\tn = len(arr)\n\t\tif n == 1 or d == 0:\n\t\t\treturn 1\n\t\te = [[] for i in range(n)]\n\t\tfor i in range(0, n):\n\t\t\tfor j in range(i - 1, max(0, i - d) - 1, -1):\n\t\t\t\tif arr[j] < arr[i]:\n\t\t\t\t\te[i].append(j)\n\t\t\t\telse:\n\t\t\t\t\tbreak\n\t\t\tfor j in range(i + 1, min(n - 1, i + d) + 1):\n\t\t\t\tif arr[j] < arr[i]:\n\t\t\t\t\te[i].append(j)\n\t\t\t\telse:\n\t\t\t\t\tbreak\n\t\tans = 1\n\t\tqueue = []\n\t\tcnt = [1 for i in range(n)]\n\t\tfor i in range(0, n):\n\t\t\tqueue.append([arr[i], i])\n\t\tqueue.sort()\n\t\tfor i in range(0, n):\n\t\t\tu = queue[i][1]\n\t\t\tfor v in e[u]:\n\t\t\t\tcnt[u] = max(cnt[u], cnt[v] + 1)\n\t\t\tans = max(ans, cnt[u])\n\t\treturn ans\n", "class Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\t\tn = len(arr)\n\n\t\t@lru_cache(None)\n\t\tdef dfs(i):\n\t\t\t(left, right) = (i, i)\n\t\t\tmax_range = 1\n\t\t\twhile left - 1 >= 0 and arr[left - 1] < arr[i] and (left - 1 >= i - d):\n\t\t\t\tleft -= 1\n\t\t\twhile right + 1 < n and arr[right + 1] < arr[i] and (right + 1 <= i + d):\n\t\t\t\tright += 1\n\t\t\tfor nxt in range(left, right + 1):\n\t\t\t\tif nxt != i:\n\t\t\t\t\tmax_range = max(max_range, 1 + dfs(nxt))\n\t\t\treturn max_range\n\t\treturn max((dfs(i) for i in range(n)))\n", "class Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\t\tv = []\n\t\tn = len(arr)\n\t\tfor i in range(n):\n\t\t\tv.append((arr[i], i))\n\t\tv = sorted(v)\n\t\tf = [-1] * n\n\t\tans = -1\n\t\tfor i in range(n):\n\t\t\tidx = v[i][1]\n\t\t\tf[idx] = 1\n\t\t\tfor j in range(1, d + 1):\n\t\t\t\tif idx - j >= 0 and arr[idx - j] < arr[idx]:\n\t\t\t\t\tf[idx] = max(f[idx], f[idx - j] + 1)\n\t\t\t\telse:\n\t\t\t\t\tbreak\n\t\t\tfor j in range(1, d + 1):\n\t\t\t\tif idx + j < n and arr[idx + j] < arr[idx]:\n\t\t\t\t\tf[idx] = max(f[idx], f[idx + j] + 1)\n\t\t\t\telse:\n\t\t\t\t\tbreak\n\t\t\tans = max(ans, f[idx])\n\t\treturn ans\n", "def bfs(arr, i, d, memo):\n\tif i in memo:\n\t\treturn memo[i]\n\tres = 1\n\tfor j in range(max(i - 1, 0), max(i - d - 1, -1), -1):\n\t\tif arr[j] >= arr[i]:\n\t\t\tbreak\n\t\tres = max(res, bfs(arr, j, d, memo) + 1)\n\tfor j in range(i + 1, min(i + d + 1, len(arr))):\n\t\tif arr[j] >= arr[i]:\n\t\t\tbreak\n\t\tres = max(res, bfs(arr, j, d, memo) + 1)\n\tmemo[i] = res\n\treturn res\n\nclass Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\t\tmemo = dict()\n\t\treturn max((bfs(arr, i, d, memo) for i in range(len(arr))))\n", "class Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\t\tn = len(arr)\n\t\tdp = [1 for i in range(n)]\n\n\t\t@lru_cache(None)\n\t\tdef rec(i):\n\t\t\tj = 1\n\t\t\twhile j <= d and i - j >= 0 and (arr[i - j] < arr[i]):\n\t\t\t\tdp[i] = max(dp[i], 1 + rec(i - j))\n\t\t\t\tj += 1\n\t\t\tj = 1\n\t\t\twhile j <= d and i + j < n and (arr[i + j] < arr[i]):\n\t\t\t\tdp[i] = max(dp[i], 1 + rec(i + j))\n\t\t\t\tj += 1\n\t\t\treturn dp[i]\n\t\tfor k in range(n):\n\t\t\trec(k)\n\t\treturn max(dp)\n", "class Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\t\t(A, n) = (arr, len(arr))\n\t\t(s, stack) = ([1] * (n + 1), [])\n\t\tfor (i, x) in enumerate(A + [float('inf')]):\n\t\t\twhile stack and A[stack[-1]] < x:\n\t\t\t\tqueue = [stack.pop()]\n\t\t\t\twhile stack and A[stack[-1]] == A[queue[-1]]:\n\t\t\t\t\tqueue.append(stack.pop())\n\t\t\t\tfor j in queue:\n\t\t\t\t\tif i - j <= d:\n\t\t\t\t\t\ts[i] = max(s[i], s[j] + 1)\n\t\t\t\t\tif stack and j - stack[-1] <= d:\n\t\t\t\t\t\ts[stack[-1]] = max(s[stack[-1]], s[j] + 1)\n\t\t\tstack.append(i)\n\t\treturn max(s[:-1])\n", "class Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\t\tvisited = {}\n\t\tarrLen = len(arr)\n\n\t\tdef check(i0):\n\t\t\tif i0 in visited:\n\t\t\t\treturn visited[i0]\n\t\t\tdi = 1\n\t\t\tpreV = 0\n\t\t\tsubAns = 1\n\t\t\twhile di <= d and i0 + di < arrLen and (arr[i0 + di] < arr[i0]):\n\t\t\t\tif arr[i0 + di] >= preV:\n\t\t\t\t\tsubAns = max(subAns, 1 + check(i0 + di))\n\t\t\t\tpreV = max(preV, arr[i0 + di])\n\t\t\t\tdi += 1\n\t\t\tdi = 1\n\t\t\tpreV = 0\n\t\t\twhile di <= d and i0 - di >= 0 and (arr[i0 - di] < arr[i0]):\n\t\t\t\tif arr[i0 - di] >= preV:\n\t\t\t\t\tsubAns = max(subAns, 1 + check(i0 - di))\n\t\t\t\tpreV = max(preV, arr[i0 - di])\n\t\t\t\tdi += 1\n\t\t\tvisited[i0] = subAns\n\t\t\treturn subAns\n\t\tans = 1\n\t\tfor i in range(arrLen):\n\t\t\tans = max(ans, check(i))\n\t\treturn ans\n", "class Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\t\tres = 0\n\t\tn = len(arr)\n\t\tself.m = [0] * n\n\t\tfor i in range(n):\n\t\t\tans = self.dfs(arr, d, i)\n\t\t\tres = max(ans, res)\n\t\treturn res\n\n\tdef dfs(self, arr, d, i):\n\t\tres = 1\n\t\tif self.m[i] != 0:\n\t\t\treturn self.m[i]\n\t\tfor k in range(1, d + 1):\n\t\t\tif i + k >= len(arr):\n\t\t\t\tbreak\n\t\t\tif arr[i + k] >= arr[i]:\n\t\t\t\tbreak\n\t\t\tans = self.dfs(arr, d, i + k) + 1\n\t\t\tif ans > res:\n\t\t\t\tres = ans\n\t\tfor k in range(1, d + 1):\n\t\t\tif i - k < 0:\n\t\t\t\tbreak\n\t\t\tif arr[i - k] >= arr[i]:\n\t\t\t\tbreak\n\t\t\tans = self.dfs(arr, d, i - k) + 1\n\t\t\tif ans > res:\n\t\t\t\tres = ans\n\t\tself.m[i] = res\n\t\treturn res\n", "class Solution:\n\n\tdef maxJumps(self, A: List[int], d: int) -> int:\n\t\tn = len(A)\n\t\tdp = [1] * n\n\t\tfor (a, i) in sorted(([a, i] for (i, a) in enumerate(A))):\n\t\t\tj = i - 1\n\t\t\twhile j >= 0 and A[j] < A[i] and (i - j <= d):\n\t\t\t\tdp[i] = max(dp[i], dp[j] + 1)\n\t\t\t\tj -= 1\n\t\t\tj = i + 1\n\t\t\twhile j < n and A[j] < A[i] and (j - i <= d):\n\t\t\t\tdp[i] = max(dp[i], dp[j] + 1)\n\t\t\t\tj += 1\n\t\treturn max(dp)\n", "class Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\t\tn = len(arr)\n\t\tif n <= 1:\n\t\t\treturn n\n\t\tvisited = [False for i in range(n)]\n\t\tL_neighbor = {}\n\t\tR_neighbor = {}\n\t\tfor i in range(n):\n\t\t\tL_neighbor[i] = i\n\t\t\tR_neighbor[i] = i\n\t\tdec = deque()\n\t\tdec.append(0)\n\t\tfor i in range(1, n):\n\t\t\twhile len(dec) > 0:\n\t\t\t\tif dec[0] < i - d:\n\t\t\t\t\tdec.popleft()\n\t\t\t\telse:\n\t\t\t\t\tbreak\n\t\t\twhile len(dec) > 0:\n\t\t\t\tif arr[dec[len(dec) - 1]] < arr[i]:\n\t\t\t\t\tdec.pop()\n\t\t\t\telse:\n\t\t\t\t\tbreak\n\t\t\tif len(dec) == 0:\n\t\t\t\tL_neighbor[i] = max(i - d, 0)\n\t\t\t\tdec.append(i)\n\t\t\telse:\n\t\t\t\tL_neighbor[i] = max(dec[len(dec) - 1] + 1, i - d, 0)\n\t\t\t\tdec.append(i)\n\t\tdec = deque()\n\t\tdec.append(n - 1)\n\t\tfor i in range(n - 2, -1, -1):\n\t\t\twhile len(dec) > 0:\n\t\t\t\tif dec[0] > i + d:\n\t\t\t\t\tdec.popleft()\n\t\t\t\telse:\n\t\t\t\t\tbreak\n\t\t\twhile len(dec) > 0:\n\t\t\t\tif arr[dec[len(dec) - 1]] < arr[i]:\n\t\t\t\t\tdec.pop()\n\t\t\t\telse:\n\t\t\t\t\tbreak\n\t\t\tif len(dec) == 0:\n\t\t\t\tR_neighbor[i] = min(i + d, n - 1)\n\t\t\t\tdec.append(i)\n\t\t\telse:\n\t\t\t\tR_neighbor[i] = min(dec[len(dec) - 1] - 1, i + d, n - 1)\n\t\t\t\tdec.append(i)\n\t\tres = 0\n\t\tlimit = [0 for i in range(n)]\n\t\tfor i in range(n):\n\t\t\tself.maxJumpDFS(i, arr, L_neighbor, R_neighbor, visited, limit)\n\t\tfor i in range(n):\n\t\t\tif res < limit[i]:\n\t\t\t\tres = limit[i]\n\t\treturn res\n\n\tdef maxJumpDFS(self, start, arr, L_neighbor, R_neighbor, visited, limit):\n\t\tif visited[start]:\n\t\t\treturn limit[start]\n\t\telse:\n\t\t\tcurrmax = 0\n\t\t\tfor i in range(L_neighbor[start], R_neighbor[start] + 1):\n\t\t\t\tif i == start:\n\t\t\t\t\tcontinue\n\t\t\t\tcurr = self.maxJumpDFS(i, arr, L_neighbor, R_neighbor, visited, limit)\n\t\t\t\tif currmax < curr:\n\t\t\t\t\tcurrmax = curr\n\t\t\tvisited[start] = True\n\t\t\tlimit[start] = currmax + 1\n\t\t\treturn limit[start]\n", "class Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\t\tmaxPath = 0\n\t\tmemory = {i: 0 for i in range(len(arr))}\n\t\tfor i in range(len(arr)):\n\t\t\tmaxPath = max(maxPath, self.dfs(i, d, arr, len(arr), memory))\n\t\treturn maxPath\n\n\tdef dfs(self, index, d, arr, arrLen, memory):\n\t\tif memory[index] != 0:\n\t\t\treturn memory[index]\n\t\tcurrentMax = 0\n\t\tfor i in range(index + 1, index + d + 1):\n\t\t\tif i >= arrLen or arr[index] <= arr[i]:\n\t\t\t\tbreak\n\t\t\tcurrentMax = max(currentMax, self.dfs(i, d, arr, arrLen, memory))\n\t\tfor i in range(index - 1, index - d - 1, -1):\n\t\t\tif i < 0 or arr[index] <= arr[i]:\n\t\t\t\tbreak\n\t\t\tcurrentMax = max(currentMax, self.dfs(i, d, arr, arrLen, memory))\n\t\tmemory[index] = currentMax + 1\n\t\treturn memory[index]\n", "class Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\t\tn = len(arr)\n\t\ti2h = {}\n\t\tfor (i, h) in enumerate(arr):\n\t\t\ti2h[i] = (h, i)\n\t\tdp = [1] * n\n\t\tfor (h, idx) in sorted(i2h.values(), key=lambda hi: hi[0]):\n\t\t\tj = idx + 1\n\t\t\twhile j <= min(n - 1, idx + d) and arr[idx] > arr[j]:\n\t\t\t\tdp[idx] = max(dp[idx], dp[j] + 1)\n\t\t\t\tj += 1\n\t\t\tj = idx - 1\n\t\t\twhile j >= max(0, idx - d) and arr[idx] > arr[j]:\n\t\t\t\tdp[idx] = max(dp[idx], dp[j] + 1)\n\t\t\t\tj -= 1\n\t\treturn max(dp)\n\n\tdef maxJumps__(self, arr: List[int], d: int) -> int:\n\t\tn = len(arr)\n\t\tmemo = [0] * n\n\n\t\tdef dfs(idx):\n\t\t\tif memo[idx]:\n\t\t\t\treturn memo[idx]\n\t\t\tjump = 1\n\t\t\tj = idx + 1\n\t\t\twhile j <= min(n - 1, idx + d) and arr[idx] > arr[j]:\n\t\t\t\tjump = max(jump, dfs(j) + 1)\n\t\t\t\tj += 1\n\t\t\tj = idx - 1\n\t\t\twhile j >= max(0, idx - d) and arr[idx] > arr[j]:\n\t\t\t\tjump = max(jump, dfs(j) + 1)\n\t\t\t\tj -= 1\n\t\t\tmemo[idx] = jump\n\t\t\treturn jump\n\t\tmax_val = 0\n\t\tfor i in range(n):\n\t\t\tmax_val = max(max_val, dfs(i))\n\t\treturn max_val\n\n\tdef maxJumps_(self, arr: List[int], d: int) -> int:\n\n\t\tdef backtracking(idx):\n\t\t\tnonlocal memo, max_val\n\t\t\tif idx in memo:\n\t\t\t\treturn memo[idx]\n\t\t\tlstack = []\n\t\t\trstack = []\n\t\t\tlbarrier = False\n\t\t\trbarrier = False\n\t\t\tfor i in range(1, d + 1):\n\t\t\t\tif not lbarrier and idx - i >= 0 and (arr[idx - i] < arr[idx]):\n\t\t\t\t\tlstack.append(idx - i)\n\t\t\t\telse:\n\t\t\t\t\tlbarrier = True\n\t\t\t\tif not rbarrier and idx + i < len(arr) and (arr[idx + i] < arr[idx]):\n\t\t\t\t\trstack.append(idx + i)\n\t\t\t\telse:\n\t\t\t\t\trbarrier = True\n\t\t\tljump = 1\n\t\t\twhile lstack:\n\t\t\t\tlidx = lstack.pop()\n\t\t\t\tljump = max(ljump, 1 + backtracking(lidx))\n\t\t\trjump = 1\n\t\t\twhile rstack:\n\t\t\t\tridx = rstack.pop()\n\t\t\t\trjump = max(rjump, 1 + backtracking(ridx))\n\t\t\tjump = max(ljump, rjump)\n\t\t\tmemo[idx] = jump\n\t\t\tmax_val = max(max_val, jump)\n\t\t\treturn jump\n\t\tmemo = {}\n\t\tmax_val = 0\n\t\tfor i in range(len(arr)):\n\t\t\tbacktracking(i)\n\t\treturn max_val\n", "class Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\t\tn = len(arr)\n\t\tres = [0] * n\n\n\t\tdef dp(i):\n\t\t\tif res[i]:\n\t\t\t\treturn res[i]\n\t\t\tres[i] = 1\n\t\t\tfor di in [-1, 1]:\n\t\t\t\tfor j in range(i + di, i + d * di + di, di):\n\t\t\t\t\tif not (0 <= j < n and arr[j] < arr[i]):\n\t\t\t\t\t\tbreak\n\t\t\t\t\tres[i] = max(res[i], dp(j) + 1)\n\t\t\treturn res[i]\n\t\treturn max(map(dp, range(n)))\n", "class Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\t\tarr.append(10 ** 6)\n\t\tn = len(arr)\n\t\tdp = [1] * n\n\t\tstack = []\n\t\tresult = 0\n\t\tfor (i, a) in enumerate(arr):\n\t\t\twhile stack and arr[stack[-1]] < a:\n\t\t\t\tfor j in range(len(stack) - 2, -1, -1):\n\t\t\t\t\tif arr[stack[j]] != arr[stack[j + 1]]:\n\t\t\t\t\t\tbreak\n\t\t\t\telse:\n\t\t\t\t\tj = -1\n\t\t\t\tfor k in range(len(stack) - j - 1):\n\t\t\t\t\tl = stack.pop()\n\t\t\t\t\tif i - l <= d:\n\t\t\t\t\t\tdp[i] = max(dp[i], 1 + dp[l])\n\t\t\t\t\tif j >= 0 and l - stack[j] <= d:\n\t\t\t\t\t\tdp[stack[j]] = max(dp[stack[j]], 1 + dp[l])\n\t\t\tstack.append(i)\n\t\tdp.pop()\n\t\treturn max(dp)\n", "class Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\t\tn = len(arr)\n\t\tjumps = [1] * n\n\n\t\tdef get_neighs(cur):\n\t\t\tneighs = []\n\t\t\tdirections = [1, -1]\n\t\t\tfor dire in directions:\n\t\t\t\tfor i in range(cur + dire, cur + (d + 1) * dire, dire):\n\t\t\t\t\tif i < 0 or i >= n:\n\t\t\t\t\t\tbreak\n\t\t\t\t\tif arr[i] >= arr[cur]:\n\t\t\t\t\t\tbreak\n\t\t\t\t\tneighs.append(i)\n\t\t\treturn neighs\n\n\t\t@lru_cache(None)\n\t\tdef dp(cur):\n\t\t\tfor neigh in get_neighs(cur):\n\t\t\t\tjumps[cur] = max(jumps[cur], dp(neigh) + 1)\n\t\t\treturn jumps[cur]\n\t\tfor i in range(len(arr)):\n\t\t\tdp(i)\n\t\treturn max(jumps)\n", "class Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\t\tm = len(arr)\n\t\tmemo = [-1 for _ in range(m)]\n\n\t\tdef dfs(i):\n\t\t\tif memo[i] != -1:\n\t\t\t\treturn memo[i]\n\t\t\tmemo[i] = 1\n\t\t\tleft = i - 1\n\t\t\twhile left >= 0 and i - left <= d and (arr[left] < arr[i]):\n\t\t\t\tmemo[i] = max(dfs(left) + 1, memo[i])\n\t\t\t\tleft -= 1\n\t\t\tright = i + 1\n\t\t\twhile right < m and right - i <= d and (arr[right] < arr[i]):\n\t\t\t\tmemo[i] = max(dfs(right) + 1, memo[i])\n\t\t\t\tright += 1\n\t\t\treturn memo[i]\n\t\tfor i in range(m):\n\t\t\tdfs(i)\n\t\tprint(memo)\n\t\treturn max(memo)\n", "class Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\t\tif not arr:\n\t\t\treturn 0\n\t\tresult = [0] * len(arr)\n\n\t\tdef _helper(i: int) -> int:\n\t\t\tif result[i]:\n\t\t\t\treturn result[i]\n\t\t\tresult[i] = 1\n\t\t\tj = 1\n\t\t\twhile j <= d and i + j < len(arr) and (arr[i + j] < arr[i]):\n\t\t\t\tresult[i] = max(result[i], _helper(i + j) + 1)\n\t\t\t\tj += 1\n\t\t\tj = 1\n\t\t\twhile j <= d and i - j >= 0 and (arr[i - j] < arr[i]):\n\t\t\t\tresult[i] = max(result[i], _helper(i - j) + 1)\n\t\t\t\tj += 1\n\t\t\treturn result[i]\n\t\tfor i in range(len(arr)):\n\t\t\t_helper(i)\n\t\treturn max(result)\n", "class Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\n\t\t@lru_cache(None)\n\t\tdef helper(idx):\n\t\t\tans = 1\n\t\t\t(ub, lb) = (1, 1)\n\t\t\twhile ub <= d or lb <= d:\n\t\t\t\tif idx + ub < len(arr) and arr[idx + ub] < arr[idx]:\n\t\t\t\t\tans = max(ans, 1 + helper(idx + ub))\n\t\t\t\t\tub += 1\n\t\t\t\telse:\n\t\t\t\t\tub = sys.maxsize\n\t\t\t\tif idx - lb >= 0 and arr[idx - lb] < arr[idx]:\n\t\t\t\t\tans = max(ans, 1 + helper(idx - lb))\n\t\t\t\t\tlb += 1\n\t\t\t\telse:\n\t\t\t\t\tlb = sys.maxsize\n\t\t\treturn ans\n\t\treturn max([helper(idx) for idx in range(len(arr))])\n", "class Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\t\tarr1 = [[i, v] for (i, v) in enumerate(arr)]\n\t\tarr1.sort(key=lambda x: x[1])\n\t\tdp = [0] * len(arr)\n\n\t\tdef dfs(start, arr, dp):\n\t\t\tif dp[start] != 0:\n\t\t\t\treturn dp[start]\n\t\t\tdp[start] = 1\n\t\t\tfor i in range(start - 1, max(start - d - 1, -1), -1):\n\t\t\t\tif arr[start] <= arr[i]:\n\t\t\t\t\tbreak\n\t\t\t\tdp[start] = max(dp[start], dfs(i, arr, dp) + 1)\n\t\t\tfor i in range(start + 1, min(start + d + 1, len(arr))):\n\t\t\t\tif arr[start] <= arr[i]:\n\t\t\t\t\tbreak\n\t\t\t\tdp[start] = max(dp[start], dfs(i, arr, dp) + 1)\n\t\t\treturn dp[start]\n\t\tfor i in range(len(arr1)):\n\t\t\tdfs(arr1[i][0], arr, dp)\n\t\treturn max(dp)\n", "class Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\t\tmax_less_than = []\n\n\t\tdef jump(iter):\n\t\t\tres = [None for i in range(len(arr))]\n\t\t\tstack = deque([])\n\t\t\tfor i in iter:\n\t\t\t\twhile stack and abs(i - stack[0]) > d:\n\t\t\t\t\tstack.popleft()\n\t\t\t\twhile stack and arr[i] > arr[stack[-1]]:\n\t\t\t\t\tlatest_poped = stack.pop()\n\t\t\t\t\tres[latest_poped] = i\n\t\t\t\tstack.append(i)\n\t\t\treturn res\n\t\tmax_less_than.append(jump(range(len(arr))))\n\t\tmax_less_than.append(jump(reversed(range(len(arr)))))\n\n\t\t@lru_cache(None)\n\t\tdef dp(i):\n\t\t\tif i is None:\n\t\t\t\treturn 0\n\t\t\treturn max(map(dp, [max_less_than[0][i], max_less_than[1][i]]), default=0) + 1\n\t\treturn max(map(dp, range(len(arr))))\n", "class Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\t\tmemo = [0] * len(arr)\n\n\t\tdef jump(i):\n\t\t\tif memo[i]:\n\t\t\t\treturn memo[i]\n\t\t\tans = 1\n\t\t\tfor di in [-1, 1]:\n\t\t\t\tfor x in range(1, d + 1):\n\t\t\t\t\tj = di * x + i\n\t\t\t\t\tif 0 <= j < len(arr) and arr[j] < arr[i]:\n\t\t\t\t\t\tans = max(ans, jump(j) + 1)\n\t\t\t\t\telse:\n\t\t\t\t\t\tbreak\n\t\t\tmemo[i] = ans\n\t\t\treturn memo[i]\n\t\tans = 0\n\t\tfor i in range(len(arr)):\n\t\t\tans = max(ans, jump(i))\n\t\treturn ans\n", "from functools import lru_cache\n\nclass Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\n\t\t@lru_cache(None)\n\t\tdef jump(idx):\n\t\t\t(l, r) = (idx - 1, idx + 1)\n\t\t\t(ans, lans, rans) = (1, 0, 0)\n\t\t\twhile l >= max(idx - d, 0) and arr[idx] > arr[l]:\n\t\t\t\tlans = max(lans, jump(l))\n\t\t\t\tl -= 1\n\t\t\twhile r <= min(len(arr) - 1, idx + d) and arr[idx] > arr[r]:\n\t\t\t\trans = max(rans, jump(r))\n\t\t\t\tr += 1\n\t\t\treturn ans + max(rans, lans)\n\t\tans = 0\n\t\tfor i in range(len(arr)):\n\t\t\tans = max(ans, jump(i))\n\t\treturn ans\n", "class Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\n\t\tdef helper(i):\n\t\t\tif cache[i]:\n\t\t\t\treturn cache[i]\n\t\t\tnumberOfJump = 0\n\t\t\tfor j in range(i + 1, i + d + 1):\n\t\t\t\tif j >= len(arr) or arr[j] >= arr[i]:\n\t\t\t\t\tbreak\n\t\t\t\tnumberOfJump = max(helper(j), numberOfJump)\n\t\t\tfor j in range(i - 1, i - d - 1, -1):\n\t\t\t\tif j < 0 or arr[j] >= arr[i]:\n\t\t\t\t\tbreak\n\t\t\t\tnumberOfJump = max(helper(j), numberOfJump)\n\t\t\tcache[i] = 1 + numberOfJump\n\t\t\treturn cache[i]\n\t\tcache = [0] * len(arr)\n\t\tans = 0\n\t\tfor i in range(len(arr)):\n\t\t\tans = max(helper(i), ans)\n\t\treturn ans\n", "class Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\t\tdp = [0] * len(arr)\n\n\t\tdef get_dp(i):\n\t\t\tif dp[i] == 0:\n\t\t\t\tdp[i] = 1\n\t\t\t\tj = i - 1\n\t\t\t\twhile j >= 0 and arr[i] > arr[j] and (i - j <= d):\n\t\t\t\t\tdp[i] = max(dp[i], 1 + get_dp(j))\n\t\t\t\t\tj -= 1\n\t\t\t\tj = i + 1\n\t\t\t\twhile j < len(arr) and arr[i] > arr[j] and (j - i <= d):\n\t\t\t\t\tdp[i] = max(dp[i], 1 + get_dp(j))\n\t\t\t\t\tj += 1\n\t\t\treturn dp[i]\n\t\tmax_count = 0\n\t\tfor i in range(len(arr)):\n\t\t\tmax_count = max(max_count, get_dp(i))\n\t\treturn max_count\n", "class Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\t\tmemo = [-1] * len(arr)\n\n\t\tdef dfs(i):\n\t\t\tif i < 0 or i >= len(arr):\n\t\t\t\treturn 0\n\t\t\tif memo[i] > 0:\n\t\t\t\treturn memo[i]\n\t\t\tmemo[i] = 1\n\t\t\tfor j in reversed(list(range(max(0, i - d), i))):\n\t\t\t\tif arr[j] >= arr[i]:\n\t\t\t\t\tbreak\n\t\t\t\tmemo[i] = max(memo[i], dfs(j) + 1)\n\t\t\tfor j in range(i + 1, min(len(arr), i + d + 1)):\n\t\t\t\tif arr[j] >= arr[i]:\n\t\t\t\t\tbreak\n\t\t\t\tmemo[i] = max(memo[i], dfs(j) + 1)\n\t\t\treturn memo[i]\n\t\treturn max((dfs(i) for i in range(len(arr))))\n", "class Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\t\tdp = {}\n\n\t\tdef jump(i):\n\t\t\tif i in dp:\n\t\t\t\treturn dp[i]\n\t\t\tm = 1\n\t\t\tstep = 1\n\t\t\twhile i + step < len(arr) and step <= d:\n\t\t\t\tif arr[i] <= arr[i + step]:\n\t\t\t\t\tbreak\n\t\t\t\tm = max(m, jump(i + step) + 1)\n\t\t\t\tstep += 1\n\t\t\tstep = 1\n\t\t\twhile i - step >= 0 and step <= d:\n\t\t\t\tif arr[i] <= arr[i - step]:\n\t\t\t\t\tbreak\n\t\t\t\tm = max(m, jump(i - step) + 1)\n\t\t\t\tstep += 1\n\t\t\tdp[i] = m\n\t\t\treturn m\n\t\tans = 0\n\t\tfor i in range(len(arr)):\n\t\t\tif i not in dp:\n\t\t\t\tjump(i)\n\t\t\tans = max(ans, dp[i])\n\t\treturn ans\n", "from functools import lru_cache\n\nclass Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\t\tn = len(arr)\n\t\tcanJumpRight = collections.defaultdict(set)\n\t\tdeque = collections.deque()\n\t\tfor i in range(n):\n\t\t\tif not deque:\n\t\t\t\tdeque.append(i)\n\t\t\telif arr[i] < arr[deque[-1]]:\n\t\t\t\tdeque.append(i)\n\t\t\telse:\n\t\t\t\ttemp = collections.deque()\n\t\t\t\twhile deque and arr[deque[-1]] <= arr[i]:\n\t\t\t\t\tcurr = deque.pop()\n\t\t\t\t\tif deque and curr - deque[-1] <= d:\n\t\t\t\t\t\tcanJumpRight[deque[-1]].add(curr)\n\t\t\t\t\t\tfor idx in canJumpRight[curr]:\n\t\t\t\t\t\t\tif idx - deque[-1] <= d:\n\t\t\t\t\t\t\t\tcanJumpRight[deque[-1]].add(idx)\n\t\t\t\tdeque.append(i)\n\t\twhile deque:\n\t\t\tcurr = deque.pop()\n\t\t\tif deque and curr - deque[-1] <= d:\n\t\t\t\tcanJumpRight[deque[-1]].add(curr)\n\t\t\t\tfor idx in canJumpRight[curr]:\n\t\t\t\t\tif idx - deque[-1] <= d:\n\t\t\t\t\t\tcanJumpRight[deque[-1]].add(idx)\n\t\tcanJumpLeft = collections.defaultdict(set)\n\t\tfor i in range(n - 1, -1, -1):\n\t\t\tif not deque:\n\t\t\t\tdeque.append(i)\n\t\t\telif arr[i] < arr[deque[-1]]:\n\t\t\t\tdeque.append(i)\n\t\t\telse:\n\t\t\t\twhile deque and arr[deque[-1]] <= arr[i]:\n\t\t\t\t\tcurr = deque.pop()\n\t\t\t\t\tif deque and abs(curr - deque[-1]) <= d:\n\t\t\t\t\t\tcanJumpLeft[deque[-1]].add(curr)\n\t\t\t\t\t\tfor idx in canJumpLeft[curr]:\n\t\t\t\t\t\t\tif abs(idx - deque[-1]) <= d:\n\t\t\t\t\t\t\t\tcanJumpLeft[deque[-1]].add(idx)\n\t\t\t\tdeque.append(i)\n\t\twhile deque:\n\t\t\tcurr = deque.pop()\n\t\t\tif deque and abs(curr - deque[-1]) <= d:\n\t\t\t\tcanJumpLeft[deque[-1]].add(curr)\n\t\t\t\tfor idx in canJumpLeft[curr]:\n\t\t\t\t\tif abs(idx - deque[-1]) <= d:\n\t\t\t\t\t\tcanJumpLeft[deque[-1]].add(idx)\n\t\tres = 0\n\t\tarr_set = collections.defaultdict(set)\n\t\tfor i in range(n):\n\t\t\tarr_set[i] = canJumpLeft[i] | canJumpRight[i]\n\t\tres = 0\n\n\t\t@lru_cache(None)\n\t\tdef dfs(curr):\n\t\t\tnonlocal res\n\t\t\tif curr not in arr_set:\n\t\t\t\treturn 1\n\t\t\tlocal = 0\n\t\t\tfor ne in arr_set[curr]:\n\t\t\t\tlocal = max(local, dfs(ne))\n\t\t\tres = max(res, local + 1)\n\t\t\treturn local + 1\n\t\tfor i in range(n):\n\t\t\tdfs(i)\n\t\treturn res\n", "import functools\n\nclass Solution:\n\n\tdef maxJumps(self, A, d):\n\t\tN = len(A)\n\t\tgraph = collections.defaultdict(list)\n\n\t\tdef jump(iterator):\n\t\t\tstack = []\n\t\t\tfor i in iterator:\n\t\t\t\twhile stack and A[stack[-1]] < A[i]:\n\t\t\t\t\tj = stack.pop()\n\t\t\t\t\tif abs(i - j) <= d:\n\t\t\t\t\t\tgraph[j].append(i)\n\t\t\t\tstack.append(i)\n\t\tjump(range(N))\n\t\tjump(reversed(range(N)))\n\n\t\t@functools.lru_cache(maxsize=None)\n\t\tdef height(i):\n\t\t\treturn 1 + max(map(height, graph[i]), default=0)\n\t\treturn max(map(height, range(N)))\n", "class Solution:\n\n\tdef maxJumps(self, arr: List[int], dis: int) -> int:\n\t\tres = 1\n\t\td = dict()\n\t\tvisit = set()\n\t\tif len(arr) == 1:\n\t\t\treturn 1\n\t\tfor i in range(len(arr)):\n\t\t\tif i == 0:\n\t\t\t\tif arr[i] <= arr[i + 1]:\n\t\t\t\t\td[i] = 1\n\t\t\t\t\tvisit.add(i)\n\t\t\telif i == len(arr) - 1:\n\t\t\t\tif arr[i] <= arr[i - 1]:\n\t\t\t\t\td[i] = 1\n\t\t\t\t\tvisit.add(i)\n\t\t\telif arr[i] <= arr[i - 1] and arr[i] <= arr[i + 1]:\n\t\t\t\td[i] = 1\n\t\t\t\tvisit.add(i)\n\n\t\tdef dfs(index):\n\t\t\tif index not in visit:\n\t\t\t\tvisit.add(index)\n\t\t\t\tcur = 1\n\t\t\t\tfor i in range(1, dis + 1):\n\t\t\t\t\tif index - i >= 0 and arr[index - i] < arr[index]:\n\t\t\t\t\t\ttemp = dfs(index - i)\n\t\t\t\t\t\td[index - i] = temp\n\t\t\t\t\t\tcur = max(cur, 1 + temp)\n\t\t\t\t\telse:\n\t\t\t\t\t\tbreak\n\t\t\t\tfor i in range(1, dis + 1):\n\t\t\t\t\tif index + i < len(arr) and arr[index + i] < arr[index]:\n\t\t\t\t\t\ttemp = dfs(index + i)\n\t\t\t\t\t\td[index + i] = temp\n\t\t\t\t\t\tcur = max(cur, 1 + temp)\n\t\t\t\t\telse:\n\t\t\t\t\t\tbreak\n\t\t\t\treturn cur\n\t\t\telse:\n\t\t\t\treturn d[index]\n\t\tfor x in range(len(arr)):\n\t\t\tif x not in visit:\n\t\t\t\tcur = dfs(x)\n\t\t\t\td[x] = cur\n\t\t\t\tres = max(res, cur)\n\t\t\telse:\n\t\t\t\tres = max(res, d[x])\n\t\treturn res\n", "class Solution:\n\n\tdef rec(self, v):\n\t\tif self.memo[v] != -1:\n\t\t\treturn self.memo[v]\n\t\tres = 1\n\t\tfor nv in self.G[v]:\n\t\t\tres = max(res, 1 + self.rec(nv))\n\t\tself.memo[v] = res\n\t\treturn res\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\t\tn = len(arr)\n\t\tself.G = [[] for _ in range(n)]\n\t\tfor i in range(n):\n\t\t\tfor j in range(i - 1, i - d - 1, -1):\n\t\t\t\tif j < 0 or arr[j] >= arr[i]:\n\t\t\t\t\tbreak\n\t\t\t\tself.G[i].append(j)\n\t\t\tfor j in range(i + 1, i + d + 1):\n\t\t\t\tif j >= n or arr[j] >= arr[i]:\n\t\t\t\t\tbreak\n\t\t\t\tself.G[i].append(j)\n\t\tself.memo = [-1] * n\n\t\tans = 0\n\t\tfor i in range(n):\n\t\t\tans = max(ans, self.rec(i))\n\t\treturn ans\n", "class Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\t\tans = dict()\n\n\t\tdef dfs(idx):\n\t\t\tif idx in ans:\n\t\t\t\treturn\n\t\t\tans[idx] = 1\n\t\t\ti = idx - 1\n\t\t\twhile i >= 0 and idx - i <= d and (arr[i] < arr[idx]):\n\t\t\t\tdfs(i)\n\t\t\t\tans[idx] = max(ans[idx], ans[i] + 1)\n\t\t\t\ti -= 1\n\t\t\ti = idx + 1\n\t\t\twhile i < len(arr) and i - idx <= d and (arr[i] < arr[idx]):\n\t\t\t\tdfs(i)\n\t\t\t\tans[idx] = max(ans[idx], ans[i] + 1)\n\t\t\t\ti += 1\n\t\tfor i in range(len(arr)):\n\t\t\tdfs(i)\n\t\tprint(ans)\n\t\treturn max(ans.values())\n", "class Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\t\tmemo = {}\n\n\t\tdef solve(i):\n\t\t\tif i in memo:\n\t\t\t\treturn memo[i]\n\t\t\tret = 1\n\t\t\tj = i - 1\n\t\t\twhile j >= max(0, i - d) and arr[j] < arr[i]:\n\t\t\t\tret = max(ret, 1 + solve(j))\n\t\t\t\tj -= 1\n\t\t\tj = i + 1\n\t\t\twhile j <= min(len(arr) - 1, i + d) and arr[j] < arr[i]:\n\t\t\t\tret = max(ret, 1 + solve(j))\n\t\t\t\tj += 1\n\t\t\tmemo[i] = ret\n\t\t\treturn ret\n\t\tfor i in range(len(arr)):\n\t\t\tsolve(i)\n\t\treturn max(memo.values())\n", "class Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\t\tself.memo = {}\n\t\tself.result = 0\n\t\tfor i in range(len(arr)):\n\t\t\tself.dfs(arr, i, d)\n\t\treturn self.result\n\n\tdef dfs(self, arr, index, d):\n\t\tif index in self.memo:\n\t\t\treturn self.memo[index]\n\t\tresult = 0\n\t\tfor dir in [-1, 1]:\n\t\t\tfor i in range(1, d + 1):\n\t\t\t\tj = index + i * dir\n\t\t\t\tif 0 <= j < len(arr) and arr[index] > arr[j]:\n\t\t\t\t\tresult = max(result, self.dfs(arr, j, d))\n\t\t\t\telse:\n\t\t\t\t\tbreak\n\t\tself.memo[index] = result + 1\n\t\tself.result = max(self.result, result + 1)\n\t\treturn result + 1\n", "class Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\t\tN = len(arr)\n\t\tumap = [list() for i in range(N)]\n\t\tdp = [-1 for i in range(N)]\n\n\t\tdef dfs(idx: int) -> int:\n\t\t\tif idx >= N or idx < 0:\n\t\t\t\treturn 0\n\t\t\tif dp[idx] != -1:\n\t\t\t\treturn dp[idx]\n\t\t\tcurr = 0\n\t\t\tfor u in umap[idx]:\n\t\t\t\tcurr = max(curr, dfs(u))\n\t\t\tdp[idx] = curr + 1\n\t\t\treturn dp[idx]\n\t\tfor i in range(N):\n\t\t\tminIdx = max(0, i - d)\n\t\t\tmaxIdx = min(N - 1, i + d)\n\t\t\tfor t in range(i - 1, minIdx - 1, -1):\n\t\t\t\tif arr[i] > arr[t]:\n\t\t\t\t\tumap[i].append(t)\n\t\t\t\telse:\n\t\t\t\t\tbreak\n\t\t\tfor t in range(i + 1, maxIdx + 1):\n\t\t\t\tif arr[i] > arr[t]:\n\t\t\t\t\tumap[i].append(t)\n\t\t\t\telse:\n\t\t\t\t\tbreak\n\t\tresult = 0\n\t\tfor i in range(N):\n\t\t\tresult = max(result, dfs(i))\n\t\treturn result\n", "class Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\t\ta = []\n\t\tjump = [0] * len(arr)\n\t\tresult = 0\n\t\tfor i in range(len(arr)):\n\t\t\ta.append((i, arr[i]))\n\t\ta.sort(key=lambda x: x[1])\n\t\tfor i in range(len(arr)):\n\t\t\tl = a[i][0] - 1\n\t\t\tr = a[i][0] + 1\n\t\t\tm = 0\n\t\t\twhile l >= 0 and arr[l] < a[i][1] and (a[i][0] - l <= d):\n\t\t\t\tm = max(m, jump[l])\n\t\t\t\tl -= 1\n\t\t\twhile r < len(arr) and arr[r] < a[i][1] and (r - a[i][0] <= d):\n\t\t\t\tm = max(m, jump[r])\n\t\t\t\tr += 1\n\t\t\tjump[a[i][0]] = m + 1\n\t\t\tresult = max(result, m + 1)\n\t\treturn result\n", "def max_jump(a, d, memo, i):\n\tif i in memo:\n\t\treturn memo[i]\n\tmax_ = 0\n\tfor j in range(1, d + 1):\n\t\tif i + j >= len(a) or a[i + j] >= a[i]:\n\t\t\tbreak\n\t\tmax_ = max(max_, max_jump(a, d, memo, i + j))\n\tfor j in range(1, d + 1):\n\t\tif i - j < 0 or a[i - j] >= a[i]:\n\t\t\tbreak\n\t\tmax_ = max(max_, max_jump(a, d, memo, i - j))\n\tmemo[i] = max_ + 1\n\treturn max_ + 1\n\nclass Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\t\tmemo = {}\n\t\tfor i in range(len(arr)):\n\t\t\tmax_jump(arr, d, memo, i)\n\t\treturn max(memo.values())\n", "class Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\n\t\tdef dp(arr, d, dic, i, n):\n\t\t\tif dic[i] != None:\n\t\t\t\treturn dic[i]\n\t\t\tmaximum = 1\n\t\t\tupreached = False\n\t\t\tdownreached = False\n\t\t\tfor p in range(1, d + 1):\n\t\t\t\tif i + p < n and (not upreached):\n\t\t\t\t\tif arr[i + p] >= arr[i]:\n\t\t\t\t\t\tupreached = True\n\t\t\t\t\telse:\n\t\t\t\t\t\tmaximum = max(maximum, 1 + dp(arr, d, dic, i + p, n))\n\t\t\t\tif i - p >= 0 and (not downreached):\n\t\t\t\t\tif arr[i - p] >= arr[i]:\n\t\t\t\t\t\tdownreached = True\n\t\t\t\t\telse:\n\t\t\t\t\t\tmaximum = max(maximum, 1 + dp(arr, d, dic, i - p, n))\n\t\t\t\tif upreached and downreached:\n\t\t\t\t\tbreak\n\t\t\tdic[i] = maximum\n\t\t\treturn maximum\n\t\tn = len(arr)\n\t\tdic = [None] * n\n\t\tmaximum = 0\n\t\tfor i in range(n):\n\t\t\tmaximum = max(maximum, dp(arr, d, dic, i, n))\n\t\treturn maximum\n", "class Solution:\n\n\tdef maxJumps(self, arr: List[int], d: int) -> int:\n\t\tdp = [-1 for _ in range(len(arr))]\n\n\t\tdef dp_memo(x):\n\t\t\tif dp[x] != -1:\n\t\t\t\treturn dp[x]\n\t\t\tdp[x] = 1\n\t\t\tfor y in range(x - 1, x - d - 1, -1):\n\t\t\t\tif y < 0 or arr[y] >= arr[x]:\n\t\t\t\t\tbreak\n\t\t\t\tdp[x] = max(dp[x], 1 + dp_memo(y))\n\t\t\tfor y in range(x + 1, x + d + 1, +1):\n\t\t\t\tif y >= len(arr) or arr[y] >= arr[x]:\n\t\t\t\t\tbreak\n\t\t\t\tdp[x] = max(dp[x], 1 + dp_memo(y))\n\t\t\treturn dp[x]\n\t\tfor i in range(len(arr)):\n\t\t\tdp_memo(i)\n\t\tprint(dp)\n\t\treturn max(dp)\n"]

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

difficulty: MEDIUM

raw_tags: ['Array', 'Dynamic Programming', 'Sorting']

source: leetcode

tags: ['Dynamic programming', 'Sorting', 'Data structures']

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

Constraints:

1 <= arr.length <= 1000

1 <= arr[i] <= 105

1 <= d <= arr.length

question:
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:
![image](1.png)

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.

Constraints:

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

data_split: test


solutions: ["class Solution:\n\n\tdef minOperations(self, logs: List[str]) -> int:\n\t\tt = 0\n\t\tfor i in logs:\n\t\t\tif i == '../':\n\t\t\t\tt = t - 1\n\t\t\telif i == './':\n\t\t\t\tt = t\n\t\t\telse:\n\t\t\t\tt = t + 1\n\t\t\tif t < 0:\n\t\t\t\tt = 0\n\t\treturn t\n", "class Solution:\n\n\tdef minOperations(self, logs: List[str]) -> int:\n\t\tresult = 0\n\t\tfor log in logs:\n\t\t\tif log[:-1] == '..':\n\t\t\t\tresult = max(0, result - 1)\n\t\t\telif log[:-1] == '.':\n\t\t\t\tpass\n\t\t\telse:\n\t\t\t\tresult += 1\n\t\treturn result\n", "class Solution:\n\n\tdef minOperations(self, logs: List[str]) -> int:\n\t\tstack = []\n\t\tfor line in logs:\n\t\t\tif line == '../':\n\t\t\t\tif stack:\n\t\t\t\t\tstack.pop()\n\t\t\telif line == './':\n\t\t\t\tpass\n\t\t\telse:\n\t\t\t\tstack.append(line)\n\t\treturn len(stack)\n", "class Solution:\n\n\tdef minOperations(self, logs: List[str]) -> int:\n\t\tdepth = 0\n\t\tfor i in logs:\n\t\t\tif i == '../':\n\t\t\t\tdepth = max(0, depth - 1)\n\t\t\telif i != './':\n\t\t\t\tdepth += 1\n\t\treturn depth\n", "class Solution:\n\n\tdef minOperations(self, logs: List[str]) -> int:\n\t\tc = 0\n\t\ti = 0\n\t\twhile i < len(logs):\n\t\t\tif logs[i] == '../':\n\t\t\t\tif c != 0:\n\t\t\t\t\tc -= 1\n\t\t\telif logs[i] == './':\n\t\t\t\tpass\n\t\t\telse:\n\t\t\t\tc += 1\n\t\t\ti += 1\n\t\treturn c\n"]

starter_code:
class Solution:
    def minOperations(self, logs: List[str]) -> int:

difficulty: EASY

source: leetcode

tags: ['String algorithms', 'Data structures']

skill_types: ['Data structures']

raw_problem:
The Leetcode file system keeps a log each time some user performs a change folder operation.

The operations are described below:

"../" : Move to the parent folder of the current folder. (If you are already in the main folder, remain in the same folder).

"./" : Remain in the same folder.

"x/" : Move to the child folder named x (This folder is guaranteed to always exist).

You are given a list of strings logs where logs[i] is the operation performed by the user at the ith step.

The file system starts in the main folder, then the operations in logs are performed.

Return the minimum number of operations needed to go back to the main folder after the change folder operations.

Example 1:

Input: logs = ["d1/","d2/","../","d21/","./"]
Output: 2
Explanation: Use this change folder operation "../" 2 times and go back to the main folder.

Example 2:

Input: logs = ["d1/","d2/","./","d3/","../","d31/"]
Output: 3

Example 3:

Input: logs = ["d1/","../","../","../"]
Output: 0

Constraints:

1 <= logs.length <= 103

2 <= logs[i].length <= 10

logs[i] contains lowercase English letters, digits, '.', and '/'.

logs[i] follows the format described in the statement.

Folder names consist of lowercase English letters and digits.

question:
The Leetcode file system keeps a log each time some user performs a change folder operation.
The operations are described below:

- "../" : Move to the parent folder of the current folder. (If you are already in the main folder, remain in the same folder).
- "./" : Remain in the same folder.
- "x/" : Move to the child folder named x (This folder is guaranteed to always exist).

You are given a list of strings logs where logs[i] is the operation performed by the user at the i^{th} step.
The file system starts in the main folder, then the operations in logs are performed.
Return the minimum number of operations needed to go back to the main folder after the change folder operations.

Example 1:
![image](1.png)

Input: logs = ["d1/","d2/","../","d21/","./"]
Output: 2
Explanation: Use this change folder operation "../" 2 times and go back to the main folder.

Example 2:
![image](2.png)

Input: logs = ["d1/","d2/","./","d3/","../","d31/"]
Output: 3

Example 3:

Input: logs = ["d1/","../","../","../"]
Output: 0

Constraints:

- 1 <= logs.length <= 10^{3}
- 2 <= logs[i].length <= 10
- logs[i] contains lowercase English letters, digits, '.', and '/'.
- logs[i] follows the format described in the statement.
- Folder names consist of lowercase English letters and digits.

image_tags: Pseudocode Pseudocode

data_split: test


G1. Lucky Numbers (Easy Version)

time_limit: 3 seconds

memory_limit: 256 megabytes

source: codeforces

raw_problem:
G1. Lucky Numbers (Easy Version)

time limit per test
3 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

This is the easy version of the problem. The only difference is that in this version $$$q=1$$$. You can make hacks only if all versions of the problem are solved.

Zookeeper has been teaching his $$$q$$$ sheep how to write and how to add. The $$$i$$$-th sheep has to write exactly $$$k$$$ non-negative integers with the sum $$$n_i$$$.

Strangely, sheep have superstitions about digits and believe that the digits $$$3$$$, $$$6$$$, and $$$9$$$ are lucky. To them, the fortune of a number depends on the decimal representation of the number; the fortune of a number is equal to the sum of fortunes of its digits, and the fortune of a digit depends on its value and position and can be described by the following table. For example, the number $$$319$$$ has fortune $$$F_{2} + 3F_{0}$$$.

Each sheep wants to maximize the sum of fortune among all its $$$k$$$ written integers. Can you help them?

Input

The first line contains a single integer $$$k$$$ ($$$1 \leq k \leq 999999$$$): the number of numbers each sheep has to write.

 The next line contains six integers $$$F_0$$$, $$$F_1$$$, $$$F_2$$$, $$$F_3$$$, $$$F_4$$$, $$$F_5$$$ ($$$1 \leq F_i \leq 10^9$$$): the fortune assigned to each digit.

 The next line contains a single integer $$$q$$$ ($$$q = 1$$$): the number of sheep.

Each of the next $$$q$$$ lines contains a single integer $$$n_i$$$ ($$$1 \leq n_i \leq 999999$$$): the sum of numbers that $$$i$$$-th sheep has to write. In this version, there is only one line.

Output

Print $$$q$$$ lines, where the $$$i$$$-th line contains the maximum sum of fortune of all numbers of the $$$i$$$-th sheep. In this version, you should print only one line.

Examples

Input

3
1 2 3 4 5 6
1
57

Output

11

Input

3
1 2 3 4 5 6
1
63

Output

8

Note

In the first test case, $$$57 = 9 + 9 + 39$$$. The three $$$9$$$'s contribute $$$1 \cdot 3$$$ and $$$3$$$ at the tens position contributes $$$2 \cdot 1$$$. Hence the sum of fortune is $$$11$$$.

In the second test case, $$$63 = 35 + 19 + 9$$$. The sum of fortune is $$$8$$$.

question:
This is the easy version of the problem. The only difference is that in this version $$$q=1$$$. You can make hacks only if all versions of the problem are solved.
Zookeeper has been teaching his $$$q$$$ sheep how to write and how to add. The $$$i$$$-th sheep has to write exactly $$$k$$$ non-negative integers with the sum $$$n_i$$$.
Strangely, sheep have superstitions about digits and believe that the digits $$$3$$$, $$$6$$$, and $$$9$$$ are lucky. To them, the fortune of a number depends on the decimal representation of the number; the fortune of a number is equal to the sum of fortunes of its digits, and the fortune of a digit depends on its value and position and can be described by the following table. For example, the number $$$319$$$ has fortune $$$F_{2} + 3F_{0}$$$.
 ![image](1.png) Each sheep wants to maximize the sum of fortune among all its $$$k$$$ written integers. Can you help them?

Input
The first line contains a single integer $$$k$$$ ($$$1 \leq k \leq 999999$$$): the number of numbers each sheep has to write.
 The next line contains six integers $$$F_0$$$, $$$F_1$$$, $$$F_2$$$, $$$F_3$$$, $$$F_4$$$, $$$F_5$$$ ($$$1 \leq F_i \leq 10^9$$$): the fortune assigned to each digit.
 The next line contains a single integer $$$q$$$ ($$$q = 1$$$): the number of sheep.
Each of the next $$$q$$$ lines contains a single integer $$$n_i$$$ ($$$1 \leq n_i \leq 999999$$$): the sum of numbers that $$$i$$$-th sheep has to write. In this version, there is only one line.

Output
Print $$$q$$$ lines, where the $$$i$$$-th line contains the maximum sum of fortune of all numbers of the $$$i$$$-th sheep. In this version, you should print only one line.

Examples
Input
3
1 2 3 4 5 6
1
57

Output
11

Input
3
1 2 3 4 5 6
1
63

Output
8

Note
In the first test case, $$$57 = 9 + 9 + 39$$$. The three $$$9$$$'s contribute $$$1 \cdot 3$$$ and $$$3$$$ at the tens position contributes $$$2 \cdot 1$$$. Hence the sum of fortune is $$$11$$$.
In the second test case, $$$63 = 35 + 19 + 9$$$. The sum of fortune is $$$8$$$.

data_split: test


E. Xenia and String Problem

problem_index: E

time_limit: 1 second

memory_limit: 256 megabytes

input_output: {"inputs": ["axx\n", "aa\n", "az\n", "abaraba\n", "dsjasdjqwz\n", "aabaabadabacbaaca\n", "zdf\n", "babaaaababbba\n", "baabzazababbbbaa\n", "badabacaabaccabcabcabaabaccbacababacaabadababadabacabacabadabbacaccabaabacaababacacabadaabacabaaacaca\n", "abxxxba\n", "abacrba\n", "lkjmjsjasda\n", "xxa\n", "abababaaababababbabb\n", "arbacaba\n", "maeamcmlkdja\n", "abacara\n", "cabadadabacabadabaaac\n", "bacabadabacabaadabacabaababadabacababacabcabaaabacaadadabacabadababacabadabacaacabadabacababaabbbada\n", "aababbbaaabaab\n", "abrcaba\n", "baaababaabaabab\n", "bacdabaacabadabacaba\n", "abaaacaba\n", "a\n", "abacabr\n", "z\n", "axw\n", "za\n", "abasaba\n", "dsjasdkqwz\n", "babaaaababbbb\n", "baabzazacabbbbaa\n", "acacaaabacabaadabacacababaacabaabaccacabbadabacabacabadababadabaacababacabccabaabacbacbaccabaacabadab\n", "abxxxca\n", "lkjmjsjatda\n", "bbabbabababaaabababa\n", "arbabaca\n", "ajdklmcmaeam\n", "cbaaara\n", "cabadadacacabadabaaac\n", "bacabadabacabaadabacabaababadababababacabcabaaabacaadadabacabadababacabadabacaacabadabacababaabbbada\n", "baabaaabbbabaa\n", "baaabaaaabaabbb\n", "abacabadabacaabadcab\n", "b\n", "abaaaa\n", "baabzazacbbbbbaa\n", "acacaaabacabaadabacacababaacabaabaccacabbadabacabacabadbbabadabaacababacabccabaabacbacbaccabaacabadab\n", "cabbdadacacabadabaaac\n", "bacabddabacabaaaabacabaababadababababacabcabaaabacaadadabacabadababacabadabacaacabadabacababaabbbada\n", "baabbaabbbabaa\n", "baaabaaaabbabab\n", "fdz\n", "xax\n", "rbacaba\n", "bba\n", "yzz\n", "abacabb\n", "awx\n", "zb\n", "abataba\n", "drjasdkqwz\n", "axbxxca\n", "adtajsjmjkl\n", "wxa\n", "acababra\n", "ajdllmcmaeam\n", "cbaaasa\n", "abb\n", "aaabaa\n", "zzy\n", "aba\n", "aaaaaa\n", "zzz\n", "abacaba\n"], "outputs": ["12\n", "2\n", "2\n", "83\n", "28\n", "129\n", "12\n", "76\n", "70\n", "998\n", "34\n", "83\n", "38\n", "12\n", "186\n", "84\n", "48\n", "83\n", "474\n", "1327\n", "68\n", "83\n", "96\n", "279\n", "103\n", "1\n", "83\n", "1\n", "12\n", "2\n", "83\n", "19\n", "67\n", "61\n", "998\n", "25\n", "38\n", "186\n", "44\n", "48\n", "34\n", "249\n", "1296\n", "68\n", "60\n", "279\n", "1\n", "33\n", "52\n", "871\n", "231\n", "1220\n", "59\n", "78\n", "12\n", "12\n", "83\n", "12\n", "12\n", "83\n", "12\n", "2\n", "83\n", "19\n", "25\n", "38\n", "12\n", "44\n", "48\n", "34\n", "12\n", "33\n", "12\n", "12\n", "15\n", "12\n", "83\n"]}

question:
Xenia the coder went to The Olympiad of Informatics and got a string problem. Unfortunately, Xenia isn't fabulous in string algorithms. Help her solve the problem.
String s is a sequence of characters s_{1}s_{2}... s_{|s|}, where record |s| shows the length of the string.
Substring s[i... j] of string s is string s_{i}s_{i + 1}... s_{j}.
String s is a Gray string, if it meets the conditions:
 -  the length of string |s| is odd; -  character ![image](1.png) occurs exactly once in the string; -  either |s| = 1, or substrings ![image](2.png) and ![image](3.png) are the same and are Gray strings. For example, strings "abacaba", "xzx", "g" are Gray strings and strings "aaa", "xz", "abaxcbc" are not.
The beauty of string p is the sum of the squares of the lengths of all substrings of string p that are Gray strings. In other words, consider all pairs of values i, j (1 ≤ i ≤ j ≤ |p|). If substring p[i... j] is a Gray string, you should add (j - i + 1)^{2} to the beauty.
Xenia has got string t consisting of lowercase English letters. She is allowed to replace at most one letter of the string by any other English letter. The task is to get a string of maximum beauty.

Input
The first line contains a non-empty string t (1 ≤ |t| ≤ 10^{5}). String t only consists of lowercase English letters.

Output
Print the sought maximum beauty value Xenia can get.
Please do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

Examples
Input
zzz

Output
12

Input
aba

Output
12

Input
abacaba

Output
83

Input
aaaaaa

Output
15

Note
In the first test sample the given string can be transformed into string p = "zbz". Such string contains Gray strings as substrings p[1... 1], p[2... 2], p[3... 3] и p[1... 3]. In total, the beauty of string p gets equal to 1^{2} + 1^{2} + 1^{2} + 3^{2} = 12. You can't obtain a more beautiful string.
In the second test case it is not necessary to perform any operation. The initial string has the maximum possible beauty.

source: codeforces

raw_problem:
E. Xenia and String Problem

time limit per test
1 second

memory limit per test
256 megabytes

input
standard input

output
standard output

Xenia the coder went to The Olympiad of Informatics and got a string problem. Unfortunately, Xenia isn't fabulous in string algorithms. Help her solve the problem.

String s is a sequence of characters s1s2... s|s|, where record |s| shows the length of the string.

Substring s[i... j] of string s is string sisi + 1... sj.

String s is a Gray string, if it meets the conditions:

 the length of string |s| is odd;

 character  occurs exactly once in the string;

 either |s| = 1, or substrings  and  are the same and are Gray strings.

For example, strings "abacaba", "xzx", "g" are Gray strings and strings "aaa", "xz", "abaxcbc" are not.

The beauty of string p is the sum of the squares of the lengths of all substrings of string p that are Gray strings. In other words, consider all pairs of values i, j (1 ≤ i ≤ j ≤ |p|). If substring p[i... j] is a Gray string, you should add (j - i + 1)2 to the beauty.

Xenia has got string t consisting of lowercase English letters. She is allowed to replace at most one letter of the string by any other English letter. The task is to get a string of maximum beauty.

Input

The first line contains a non-empty string t (1 ≤ |t| ≤ 105). String t only consists of lowercase English letters.

Output

Print the sought maximum beauty value Xenia can get.

Please do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

Examples

Input

zzz

Output

12

Input

aba

Output

12

Input

abacaba

Output

83

Input

aaaaaa

Output

15

Note

In the first test sample the given string can be transformed into string p = "zbz". Such string contains Gray strings as substrings p[1... 1], p[2... 2], p[3... 3] и p[1... 3]. In total, the beauty of string p gets equal to 12 + 12 + 12 + 32 = 12. You can't obtain a more beautiful string.

In the second test case it is not necessary to perform any operation. The initial string has the maximum possible beauty.

tags: ['String algorithms', 'Dynamic programming', 'Implementation']

skill_types: ['Dynamic programming']

raw_tags: ['implementation', 'strings', 'hashing', 'dp', 'string suffix structures']

image_tags: Math Math Math

data_split: test


name: CODE FESTIVAL 2017 Elimination Tournament Round 2 (Parallel) - Many Swaps Sorting

source: atcoder

time_limit: 2.0 seconds

memory_limit: 256.0 megabytes

raw_problem:
配点 : <var>900</var> 点

問題文

すぬけくんは <var>(0,1,2, ...,N-1)</var> を並び替えて得られるような数列 <var>p</var> を持っています。
<var>p</var> の (<var>0</var>-indexedでの) <var>i</var> 番目の数は <var>p_i</var> です。

すぬけくんは <var>1,2,...,N-1</var> の番号がついた <var>N-1</var> 種類の操作を自由な順番で何度でも行うことができます。
<var>k</var> 番の操作を行うと以下のソースコードで表されるような処理が実行されます。

for(int i=k;i<N;i++)
    swap(p[i],p[i-k]);

すぬけくんは操作を <var>0</var> 回以上 <var>10^{5}</var> 回以下行って <var>p</var> を昇順に並び替えたいです。そのような操作手順の一例を示してください。
なお、この問題の制約下で、そのような操作手順が必ず存在することが証明できます。

制約

<var>2 \leq N \leq 200</var>

<var>0 \leq p_i \leq N-1</var>

<var>p</var> は <var>(0,1,2,...,N-1)</var> を並び替えて得られる

部分点

<var>300</var> 点分のデータセットでは <var>N \leq 7</var> が成立する

別の <var>400</var> 点分のデータセットでは <var>N \leq 30</var> が成立する

入力

入力は以下の形式で標準入力から与えられる。

<var>N</var>
<var>p_0</var> <var>p_1</var> <var>...</var> <var>p_{N-1}</var>

出力

操作回数(これを <var>m</var> とする)を <var>1</var> 行目に出力せよ。
続く <var>m</var> 行のうち <var>i</var> 行目には <var>i</var> 番目に実行する操作の番号を出力せよ。
<var>m</var> が <var>10^5</var> 以下であり、<var>m</var> 回の操作後に<var> p</var> が昇順となっていれば正解となる。

入力例 1

5
4 2 0 1 3

出力例 1

4
2
3
1
2

以下の図に各操作による <var>p</var> の変化を示します。

入力例 2

9
1 0 4 3 5 6 2 8 7

出力例 2

11
3
6
1
3
5
2
4
7
8
6
3

Score : <var>900</var> points

Problem Statement

Snuke has a sequence <var>p</var>, which is a permutation of <var>(0,1,2, ...,N-1)</var>.
The <var>i</var>-th element (<var>0</var>-indexed) in <var>p</var> is <var>p_i</var>.

He can perform <var>N-1</var> kinds of operations labeled <var>1,2,...,N-1</var> any number of times in any order.
When the operation labeled <var>k</var> is executed, the procedure represented by the following code will be performed:

for(int i=k;i<N;i++)
    swap(p[i],p[i-k]);

He would like to sort <var>p</var> in increasing order using between <var>0</var> and <var>10^{5}</var> operations (inclusive).
Show one such sequence of operations.
It can be proved that there always exists such a sequence of operations under the constraints in this problem.

Constraints

<var>2 \leq N \leq 200</var>

<var>0 \leq p_i \leq N-1</var>

<var>p</var> is a permutation of <var>(0,1,2,...,N-1)</var>.

Partial Scores

In the test set worth <var>300</var> points, <var>N \leq 7</var>.

In the test set worth another <var>400</var> points, <var>N \leq 30</var>.

Input

Input is given from Standard Input in the following format:

<var>N</var>
<var>p_0</var> <var>p_1</var> <var>...</var> <var>p_{N-1}</var>

Output

Let <var>m</var> be the number of operations in your solution. In the first line, print <var>m</var>.
In the <var>i</var>-th of the following <var>m</var> lines, print the label of the <var>i</var>-th executed operation.
The solution will be accepted if <var>m</var> is at most <var>10^5</var> and <var>p</var> is in increasing order after the execution of the <var>m</var> operations.

Sample Input 1

5
4 2 0 1 3

Sample Output 1

4
2
3
1
2

Each operation changes <var>p</var> as shown below:

Sample Input 2

9
1 0 4 3 5 6 2 8 7

Sample Output 2

11
3
6
1
3
5
2
4
7
8
6
3

question:
Snuke has a sequence $p$, which is a permutation of $(0,1,2, ...,N-1)$.
The $i$-th element ($0$-indexed) in $p$ is $p_i$.
He can perform $N-1$ kinds of operations labeled $1,2,...,N-1$ any number of times in any order.
When the operation labeled $k$ is executed, the procedure represented by the following code will be performed:
for(int i=k;i<N;i++)
    swap(p[i],p[i-k]);

He would like to sort $p$ in increasing order using between $0$ and $10^{5}$ operations (inclusive).
Show one such sequence of operations.
It can be proved that there always exists such a sequence of operations under the constraints in this problem.

Constraints

- $2 \leq N \leq 200$
- $0 \leq p_i \leq N-1$
- $p$ is a permutation of $(0,1,2,...,N-1)$.

Partial Scores

- In the test set worth $300$ points, $N \leq 7$.
- In the test set worth another $400$ points, $N \leq 30$.

Input
Input is given from Standard Input in the following format:
$N$

$p_0$ $p_1$ $...$ $p_{N-1}$

Output
Let $m$ be the number of operations in your solution. In the first line, print $m$.
In the $i$-th of the following $m$ lines, print the label of the $i$-th executed operation.
The solution will be accepted if $m$ is at most $10^5$ and $p$ is in increasing order after the execution of the $m$ operations.

Sample Input 1
5
4 2 0 1 3

Sample Output 1
4
2
3
1
2

- Each operation changes $p$ as shown below:

![image](1.png)

Sample Input 2
9
1 0 4 3 5 6 2 8 7

Sample Output 2
11
3
6
1
3
5
2
4
7
8
6
3

data_split: test