Given an integer array arr, you start at some index i and repeatedly jump to a larger index until you can no longer jump or you reach the last index.

A jump count starts at $1$ for the first jump, $2$ for the second jump, and so on.
For a jump from index i, you may only jump to an index j where $j > i$, and the destination j is chosen by these rules:

For an odd numbered jump (the $1$st, $3$rd, $5$th, … jump):
Select the index j such that arr[j] is the smallest value among all arr[k] with $k > i$ and arr[k] >= arr[i].
If multiple indices have the same chosen value, pick the smallest index.

For an even numbered jump (the $2$nd, $4$th, $6$th, … jump):
Select the index j such that arr[j] is the largest value among all arr[k] with $k > i$ and arr[k] <= arr[i].
If multiple indices have the same chosen value, pick the smallest index.

An index i is considered good if, starting from i and following these rules, you can eventually reach the last index of arr. Return the number of good starting indices.

Constraints:

• $1 \leq$ arr.length $\leq 2 \cdot 10^4$

• $0 \leq$ arr[i] $< 10^5$

Input: arr = [10, 13, 12, 14, 15]-List[int]
Output: 2-int
Explanation: The good starting indices are 3 and 4. From i = 3 (value 14), the first (odd) jump goes to the smallest value >= 14 on the right, which is 15 at index 4, reaching the end; i = 4 is already the last index. All other starts get stuck before reaching the end.

Input: arr = [2, 3, 1, 1, 4]-List[int]
Output: 3-int
Explanation: The good starting indices are 1, 3, and 4. From i = 1 (value 3) and i = 3 (value 1), the first (odd) jump goes to 4 at index 4, reaching the end, and i = 4 is already the last index. Starts 0 and 2 eventually get stuck because no valid next jump exists under the odd/even rules.

Input: arr = [5, 1, 3, 4, 2]-List[int]
Output: 3-int
Explanation: The good starting indices are 1, 2, and 4. From i = 1 (value 1), the odd jump goes to the smallest value >= 1 on the right, 2 at index 4 (the end). From i = 2 (value 3), the odd jump goes to 4 at index 3, then the even jump goes to the largest value <= 4 on the right, 2 at index 4 (the end). i = 4 is already the last index, while i = 0 (value 5) and i = 3 (value 4) are stuck because no value on their right is large enough for the first odd jump.

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.