<p>You are given an integer array <code>arr</code>. From some starting index, you can make a series of jumps. The (1<sup>st</sup>, 3<sup>rd</sup>, 5<sup>th</sup>, ...) jumps in the series are called <strong>odd-numbered jumps</strong>, and the (2<sup>nd</sup>, 4<sup>th</sup>, 6<sup>th</sup>, ...) jumps in the series are called <strong>even-numbered jumps</strong>. Note that the <strong>jumps</strong> are numbered, not the indices.</p>

<p>You may jump forward from index <code>i</code> to index <code>j</code> (with <code>i &lt; j</code>) in the following way:</p>

<ul>
	<li>During <strong>odd-numbered jumps</strong> (i.e., jumps 1, 3, 5, ...), you jump to the index <code>j</code> such that <code>arr[i] &lt;= arr[j]</code> and <code>arr[j]</code> is the smallest possible value. If there are multiple such indices <code>j</code>, you can only jump to the <strong>smallest</strong> such index <code>j</code>.</li>
	<li>During <strong>even-numbered jumps</strong> (i.e., jumps 2, 4, 6, ...), you jump to the index <code>j</code> such that <code>arr[i] &gt;= arr[j]</code> and <code>arr[j]</code> is the largest possible value. If there are multiple such indices <code>j</code>, you can only jump to the <strong>smallest</strong> such index <code>j</code>.</li>
	<li>It may be the case that for some index <code>i</code>, there are no legal jumps.</li>
</ul>

<p>A starting index is <strong>good</strong> if, starting from that index, you can reach the end of the array (index <code>arr.length - 1</code>) by jumping some number of times (possibly 0 or more than once).</p>

<p>Return <em>the number of <strong>good</strong> starting indices</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> arr = [10,13,12,14,15]
<strong>Output:</strong> 2
<strong>Explanation:</strong> 
From starting index i = 0, we can make our 1st jump to i = 2 (since arr[2] is the smallest among arr[1], arr[2], arr[3], arr[4] that is greater or equal to arr[0]), then we cannot jump any more.
From starting index i = 1 and i = 2, we can make our 1st jump to i = 3, then we cannot jump any more.
From starting index i = 3, we can make our 1st jump to i = 4, so we have reached the end.
From starting index i = 4, we have reached the end already.
In total, there are 2 different starting indices i = 3 and i = 4, where we can reach the end with some number of
jumps.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> arr = [2,3,1,1,4]
<strong>Output:</strong> 3
<strong>Explanation:</strong> 
From starting index i = 0, we make jumps to i = 1, i = 2, i = 3:
During our 1st jump (odd-numbered), we first jump to i = 1 because arr[1] is the smallest value in [arr[1], arr[2], arr[3], arr[4]] that is greater than or equal to arr[0].
During our 2nd jump (even-numbered), we jump from i = 1 to i = 2 because arr[2] is the largest value in [arr[2], arr[3], arr[4]] that is less than or equal to arr[1]. arr[3] is also the largest value, but 2 is a smaller index, so we can only jump to i = 2 and not i = 3
During our 3rd jump (odd-numbered), we jump from i = 2 to i = 3 because arr[3] is the smallest value in [arr[3], arr[4]] that is greater than or equal to arr[2].
We can&#39;t jump from i = 3 to i = 4, so the starting index i = 0 is not good.
In a similar manner, we can deduce that:
From starting index i = 1, we jump to i = 4, so we reach the end.
From starting index i = 2, we jump to i = 3, and then we can&#39;t jump anymore.
From starting index i = 3, we jump to i = 4, so we reach the end.
From starting index i = 4, we are already at the end.
In total, there are 3 different starting indices i = 1, i = 3, and i = 4, where we can reach the end with some
number of jumps.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> arr = [5,1,3,4,2]
<strong>Output:</strong> 3
<strong>Explanation:</strong> We can reach the end from starting indices 1, 2, and 4.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= arr.length &lt;= 2 * 10<sup>4</sup></code></li>
	<li><code>0 &lt;= arr[i] &lt; 10<sup>5</sup></code></li>
</ul>

class Solution:
    # def oddEvenJumps(self, arr: List[int]) -> int:
    #     # Time Complexity: O(n**2) simulation/ build graph
    #     odd_jump = self.get_odd_jump(arr)
    #     even_jump = self.get_even_jump(arr)
    #     res, n = 0, len(arr)
    #     for i in range(n): #枚舉起點
    #         nxt_jump = odd_jump
    #         idx = i
    #         while idx != n-1:
    #             if not nxt_jump[idx]:
    #                 break
    #             idx = nxt_jump[idx]
    #             if nxt_jump == odd_jump: # cur step
    #                 nxt_jump = even_jump # update nxt_jump w/ another jump
    #             else:
    #                 nxt_jump = odd_jump 
    #         if idx == n-1:
    #             res += 1
    #     return res

    # def get_odd_jump(self, A):
    #     jump = [None] * len(A)
    #     for i in range(len(A)):
    #         nxt_val = float('inf') #找比其大值的最小值
    #         nxt_idx = -1
    #         for j in range(i+1, len(A)):
    #             if A[j] < A[i]:
    #                 continue 
    #             if nxt_val > A[j]:
    #                 nxt_val = A[j]
    #                 nxt_idx = j
    #         if nxt_val != float('inf'):
    #             jump[i] = nxt_idx 
    #     return jump 

    # def get_even_jump(self, A):
    #     jump = [None] * len(A)
    #     for i in range(len(A)):
    #         nxt_val = -float('inf') #找比其小值的最大值
    #         nxt_idx = -1
    #         for j in range(i+1, len(A)):
    #             if A[j] > A[i]:
    #                 continue 
    #             if nxt_val < A[j]:
    #                 nxt_val =  A[j]
    #                 nxt_idx = j
    #         if nxt_val != -float('inf'):
    #             jump[i] = nxt_idx 
    #     return jump

    def oddEvenJumps(self, A: List[int]) -> int:
        # 单调栈建反向图 + BFS， 时间复杂度O(nlogn)
        graph = self.construct_graph(A)
        res = 1 
        visited = set([(len(A)-1, 0), (len(A)-1, 1)])
        queue = deque()
        queue.append((len(A)-1, 0))
        queue.append((len(A)-1, 1))
        while queue:
            cur = queue.popleft()
            for nei in graph[cur]:
                if nei not in visited:
                    queue.append(nei)
                    visited.add(nei)
                if nei[1] == 1:
                    res += 1
        return res 
    
    # def construct_graph(self, A):
    #     graph = {} # store{(idx, direction): neighbors}
    #     for i in range(len(A)):
    #         graph[(i, 0)] = []
    #         graph[(i, 1)] = []
    #     # for odd jump
    #     for i in range(len(A)):
    #         nxt_val = float('inf')
    #         nxt_idx = -1
    #         for j in range(i+1, len(A)):
    #             if A[j] < A[i]:
    #                 continue 
    #             if nxt_val > A[j]:
    #                 nxt_val = A[j]
    #                 nxt_idx = j
    #         if nxt_val != float('inf'):
    #             graph[(nxt_idx, 0)].append((i, 1))
    #     # for even jump
    #     for i in range(len(A)):
    #         nxt_val = -float('inf')
    #         nxt_idx = -1 
    #         for j in range(i+1, len(A)):
    #             if A[j] > A[i]:
    #                 continue 
    #             if nxt_val < A[j]:
    #                 nxt_val = A[j]
    #                 nxt_idx = j
    #         if nxt_val != -float('inf'):
    #             graph[(nxt_idx, 1)].append((i, 0))
    #     return graph

    def construct_graph(self, A):
        graph, stack = {}, []
        for i in range(len(A)):
            graph[(i, 0)] = []
            graph[(i, 1)] = []
        # for odd jump 
        pairs = sorted([v, i] for i, v in enumerate(A)) # ascending order
        for v, i in pairs:
            while stack and stack[-1] <= i:
                graph[(i, 0)].append((stack[-1], 1))
                stack.pop()
            stack.append(i)
        
        # for even jump
        stack = []
        pairs = sorted([-v, i] for i, v in enumerate(A)) # descending order
        for v, i in pairs:
            while stack and stack[-1] <= i:
                graph[(i, 1)].append((stack[-1], 0))
                stack.pop()
            stack.append(i)
        return graph

    # def oddEvenJumps(self, A: List[int]) -> int:
    #     # 单调栈建图+动态规划解法
    #     pairs = sorted([(value, index) for index, value in enumerate(A)])
    #     odd_jump = self.get_jump(list(reversed(pairs)))
        
    #     # for the same value, sort index in desc order.
    #     pairs = sorted(pairs, key=lambda x: (x[0], -x[1]))
    #     even_jump = self.get_jump(pairs)

    #     # dp = array of n x 2
    #     # dp[i][0] can we jump to n - 1 when we arrive i by even jumps
    #     # dp[i][1] can we jump to n - 1 when we arrive i by odd jumps
    #     n = len(A)
    #     dp = [[False, False] for _ in range(n)]
    #     dp[n - 1][0] = dp[n - 1][1] = True
        
    #     answer = 1
    #     for i in range(n - 2, -1, -1):
    #         dp[i][0] = dp[odd_jump[i]][1] if odd_jump[i] is not None else False
    #         dp[i][1] = dp[even_jump[i]][0] if even_jump[i] is not None else False
    #         if dp[i][0] == True:
    #             answer += 1
    #     return answer
        
    # def get_jump(self, pairs):
    #     jump, stack = [None] * len(pairs), []
    #     for value, index in pairs:
    #         self.mono_desc_push(stack, index)
    #         jump[index] = stack[-2] if len(stack) > 1 else None
    #     return jump
        
    # def mono_desc_push(self, stack, val):
    #     while stack and stack[-1] <= val:
    #         stack.pop()
    #     stack.append(val)
        
32970