You are given an integer array A.  From some starting index, you can make a series of jumps.  The (1st, 3rd, 5th, ...) jumps in the series are called odd numbered jumps, and the (2nd, 4th, 6th, ...) jumps in the series are called even numbered jumps.
You may from index i jump forward to index j (with i < j) in the following way:

During odd numbered jumps (ie. jumps 1, 3, 5, ...), you jump to the index j such that A[i] <= A[j] and A[j] is the smallest possible value.  If there are multiple such indexes j, you can only jump to the smallest such index j.
During even numbered jumps (ie. jumps 2, 4, 6, ...), you jump to the index j such that A[i] >= A[j] and A[j] is the largest possible value.  If there are multiple such indexes j, you can only jump to the smallest such index j.
(It may be the case that for some index i, there are no legal jumps.)

A starting index is good if, starting from that index, you can reach the end of the array (index A.length - 1) by jumping some number of times (possibly 0 or more than once.)
Return the number of good starting indexes.
 
Example 1:
Input: [10,13,12,14,15]
Output: 2
Explanation: 
From starting index i = 0, we can jump to i = 2 (since A[2] is the smallest among A[1], A[2], A[3], A[4] that is greater or equal to A[0]), then we can't jump any more.
From starting index i = 1 and i = 2, we can jump to i = 3, then we can't jump any more.
From starting index i = 3, we can jump to i = 4, so we've reached the end.
From starting index i = 4, we've reached the end already.
In total, there are 2 different starting indexes (i = 3, i = 4) where we can reach the end with some number of jumps.


Example 2:
Input: [2,3,1,1,4]
Output: 3
Explanation: 
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 A[1] is the smallest value in (A[1], A[2], A[3], A[4]) that is greater than or equal to A[0].

During our 2nd jump (even numbered), we jump from i = 1 to i = 2 because A[2] is the largest value in (A[2], A[3], A[4]) that is less than or equal to A[1].  A[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 A[3] is the smallest value in (A[3], A[4]) that is greater than or equal to A[2].

We can'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'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 indexes (i = 1, i = 3, i = 4) where we can reach the end with some number of jumps.


Example 3:
Input: [5,1,3,4,2]
Output: 3
Explanation: 
We can reach the end from starting indexes 1, 2, and 4.



 
Note:

1 <= A.length <= 20000
0 <= A[i] < 100000

Difficulty: interview

Starter code:

class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        

Solutions:
class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        def findNextHighestIdx(B: List[int]) -> List[int]:
            next_idx_list = [None] * len(B)
            stack = []
            for i in B:
                while stack and stack[-1] < i:
                    next_idx_list[stack.pop()] = i
                stack.append(i)
            return next_idx_list

        N = len(A)
        B = sorted(range(N), key=lambda i: A[i])
        oddnextidx = findNextHighestIdx(B)
        B.sort(key=lambda i: -A[i])
        evennextidx = findNextHighestIdx(B)
        
        odd = [False] * N
        odd[N-1] = True
        even = [False] * N
        even[N-1] = True
        
        for i in range(N-2, -1, -1):
            if oddnextidx[i] is not None:
                odd[i] = even[oddnextidx[i]]
            if evennextidx[i] is not None:
                even[i] = odd[evennextidx[i]]
        
        return sum(odd)

class Solution:
    def oddEvenJumps(self, A: 'List[int]') -> 'int':

        # sort indexes of A by values in A
        sorted_indexes = sorted(list(range(len(A))), key=lambda i: A[i])

        # generate list of indexes we can jump to next on odd jumps
        oddnext = self.makeStack(sorted_indexes)

        # sort indexes of A by reverse order of their value in A
        sorted_indexes.sort(key=lambda i: A[i], reverse=True)

        # generate list of indexes we can jump to next on even jumps
        evennext = self.makeStack(sorted_indexes)

        # initialize odd and even lists that will contain
        # the information of if the end can be reached
        # from the respective index
        odd = [False] * len(A)
        even = [False] * len(A)

        # the last index is always counted
        odd[-1] = even[-1] = True

        # iterate through A backwards, starting at next to last element
        for i in range(len(A) - 1, -1, -1):

            # if an odd jump is available from current index,
            # check if an even jump landed on the index of the available
            # odd jump and set current index in odd to True if it did
            if oddnext[i] is not None:
                odd[i] = even[oddnext[i]]
            # if an even jump is available from current index,
            # check if an odd jump landed on the index of the available
            # even jump and set current index in even to True if it did
            if evennext[i] is not None:
                even[i] = odd[evennext[i]]

        # return the number of spots marked True in odd
        # we always start with an odd jump, so odd will
        # contain the number of valid jumps to reach the end
        return sum(odd)

    # makes monotonic stack
    def makeStack(self, sorted_indexes):
        result = [None] * len(sorted_indexes)
        stack = []
        for i in sorted_indexes:
            while stack and i > stack[-1]:
                result[stack.pop()] = i
            stack.append(i)
        # delete stack as a memory optimization
        return result
            
                    


class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        
        N = len(A)
        
        def makeorder(sortedIdx):
            ans = [-1]*N
            stack=[]
            for i in sortedIdx:
                while stack and i>stack[-1]:
                    ans[stack[-1]]=i
                    stack.pop()
                stack.append(i)
            return ans
                
        sortedIdx = sorted(range(N), key=lambda i:A[i])
        oddNext = makeorder(sortedIdx)
        
        sortedIdx = sorted(range(N), key=lambda i:-A[i])
        evenNext = makeorder(sortedIdx)

        odd = [False]*N
        even = [False]*N
        
        odd[N-1]=True
        even[N-1]=True
        
        for i in range(N-2,-1,-1):
            if oddNext[i]!=-1:
                odd[i]=even[oddNext[i]]
            if evenNext[i]!=-1:
                even[i]=odd[evenNext[i]]
        
        return sum(odd)

EVEN = 0
ODD = 1

class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        A_sorted = []
        for i, a in enumerate(A):
            item = (a, i)
            A_sorted.append(item)
        A_sorted.sort()
        
        odd_jmp_dct = {}
        # Create dct of reversed odd jumps
        for i, item in enumerate(A_sorted):
            a, idx = item
            if idx == len(A) - 1:
                continue
            # find where a can jump to
            j = i + 1
            if j >= len(A_sorted):
                continue
            next_a, next_idx = A_sorted[j]
            while j < len(A_sorted) - 1 and next_idx < idx:
                j += 1
                next_a, next_idx = A_sorted[j]
            if next_idx > idx:
                try:
                    odd_jmp_dct[next_idx].add(idx)
                except KeyError:
                    odd_jmp_dct[next_idx] = set([idx])
        
        A_sorted.sort(key=lambda x: (-x[0], x[1]))
        even_jmp_dct = {}
        # Create dct of reversed even jumps
        for i, item in enumerate(A_sorted):
            a, idx = item
            if idx == len(A) - 1:
                continue
            # find where a can jump to
            j = i + 1
            if j >= len(A_sorted):
                continue
            next_a, next_idx = A_sorted[j]
            while j < len(A_sorted) - 1 and next_idx < idx:
                j += 1
                next_a, next_idx = A_sorted[j]
            if next_idx > idx:
                try:
                    even_jmp_dct[next_idx].add(idx)
                except KeyError:
                    even_jmp_dct[next_idx] = set([idx])
        # print(odd_jmp_dct)
        # print(even_jmp_dct)
        # Try traversing through graph from end node to any other nodes
        q = collections.deque()
        item1 = (len(A) - 1, EVEN) # (<index>, <jump type>)
        item2 = (len(A) - 1, ODD)
        q.append(item1)
        q.append(item2)
        
        ans = set([len(A) - 1])
        
        while q:
            # print(q)
            i, jump_type = q.popleft()
            if jump_type == ODD:
                if i not in odd_jmp_dct:
                    continue
                for new_i in odd_jmp_dct[i]:
                    new_item = (new_i, EVEN)
                    ans.add(new_i)
                    q.append(new_item)
            else:
                if i not in even_jmp_dct:
                    continue
                for new_i in even_jmp_dct[i]:
                    new_item = (new_i, ODD)
                    q.append(new_item)
        return len(ans)


class Solution(object):
    def oddEvenJumps(self, A):
        lenOfA = len(A)
        sortedA = sorted(range(lenOfA), key= lambda key : A[key])
        def make(array):
            toNextIndex = [None] * lenOfA
            stack = []  # invariant: stack is decreasing
            for i in array:
                while stack and i > stack[-1]:
                    toNextIndex[stack.pop()] = i
                stack.append(i)
            return toNextIndex
        nextOdd = make(sortedA)
        sortedA.sort(key=lambda key : -A[key])
        nextEven = make(sortedA)

        def update(memo, footPrints):
            for footPrint in footPrints:
                memo['%d-%s' % (footPrint[0], footPrint[1])] = None

        success = {}
        failed = {}
        output = 0
        for startIndex in range(lenOfA):
            index = startIndex
            jump = 1
            footPrints = set([])
            while index < lenOfA:
                if index == lenOfA - 1:
                    update(success, footPrints)
                    output += 1
                    break

                isOdd = jump % 2 == 1
                cacheKey = '%d-odd' % index if isOdd else '%d-even' % index
                if cacheKey in success:
                    # Don't need to check cause it found same cache key in success history
                    output += 1
                    break
                elif cacheKey in failed:
                    # Don't need to check cause it found same cache key in failed history
                    break

                if isOdd:
                    # Odd numbered jump find smallest
                    nextIndex = nextOdd[index]
                    if nextIndex is None:
                        update(failed, footPrints)
                        break
                    footPrints.add((index, 'odd'))
                else:
                    # Even numbered jump find largest
                    nextIndex = nextEven[index]
                    if nextIndex is None:
                        update(failed, footPrints)
                        break
                    footPrints.add((index, 'even'))

                index = nextIndex
                jump += 1

        return output

class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        ALen = len(A)
        moves = [[None, None] for i in range(ALen)] # [odd move, even move]
        sortedNum = [[A[-1], ALen-1]]
        
        def insertAt(x):
            l = 0
            r = len(sortedNum) - 1
            if x < sortedNum[l][0]:
                return 0
            if x > sortedNum[r][0]:
                return r + 1
            while r > l:
                m = (r + l) // 2
                if x > sortedNum[m][0]:
                    l = m + 1
                elif x < sortedNum[m][0]:
                    r = m
                else: 
                    return m
            return l
        
        
        for i in range(ALen-2, -1, -1):
            i1 = insertAt(A[i])
            if i1 < len(sortedNum) and sortedNum[i1][0] == A[i]:
                moves[i] = [sortedNum[i1][1], sortedNum[i1][1]]
                sortedNum[i1][1] = i
            else:
                if i1 == 0:
                    moves[i][0] = sortedNum[0][1]
                    moves[i][1] = None
                elif i1 == len(sortedNum):
                    moves[i][0] = None
                    moves[i][1] = sortedNum[-1][1]
                else:
                    moves[i] = [sortedNum[i1][1], sortedNum[i1-1][1]]
                sortedNum.insert(i1, [A[i], i])
        # print(sortedNum)
        # print(moves)
        goodMoveList = [[False, False] for i in range(ALen)] # [odd move, even move]
        goodMoveList[-1] = [True, True]
        ans = 1
        for i in range(ALen-2, -1, -1):
            if moves[i][0] != None and goodMoveList[moves[i][0]][1]:
                goodMoveList[i][0] = True
                ans += 1
            if moves[i][1] != None and goodMoveList[moves[i][1]][0]:
                goodMoveList[i][1] = True
        # print(goodMoveList)
        return ans
        
        
        
        
        


class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        
        n = len(A)
        next_higher, next_lower = [0]*n, [0]*n
        
        stack = []
        for a, i in sorted([a,i] for i, a in enumerate(A)):
            while stack and stack[-1] < i:
                next_higher[stack.pop()] = i
            stack.append(i)
            
        for a, i in sorted([-a,i] for i, a in enumerate(A)):
            while stack and stack[-1] < i:
                next_lower[stack.pop()] = i
            stack.append(i)
            
        higher, lower = [0]*n, [0]*n
        higher[-1] = 1
        lower[-1] = 1
        for i in range(n-1)[::-1]:
            higher[i] = lower[next_higher[i]]
            lower[i] = higher[next_lower[i]]
        return sum(higher)
#         n = len(A)
#         next_higher, next_lower = [0] * n, [0] * n

#         stack = []
#         for a, i in sorted([a, i] for i, a in enumerate(A)):
#             while stack and stack[-1] < i:
#                 next_higher[stack.pop()] = i
#             stack.append(i)

#         stack = []
#         for a, i in sorted([-a, i] for i, a in enumerate(A)):
#             while stack and stack[-1] < i:
#                 next_lower[stack.pop()] = i
#             stack.append(i)

#         print(next_higher)
#         print(next_lower)
#         higher, lower = [0] * n, [0] * n
#         higher[-1] = lower[-1] = 1
#         for i in range(n - 1)[::-1]:
#             higher[i] = lower[next_higher[i]]
#             lower[i] = higher[next_lower[i]]
#         print(higher)
#         print(lower)
#         return sum(higher)


class Solution:
    def getIndex(self, val, arr):
        start =0
        end = len(arr)-1
        while start < end:
            mid = start + (end-start)//2
            if arr[mid][0] < val:
                start = mid +1
            else:
                end = mid
        if arr[start][0] < val:
            start += 1
        return start
    
    def oddEvenJumps(self, A: List[int]) -> int:
        items = len(A)
        even = [False]*items
        odd = [False]*items
        goodindex = 1
        even[-1], odd[-1] = True, True
        vals = [[A[-1], items-1]]
        
        for index in range(items-2, -1, -1):
            insind = self.getIndex(A[index], vals )
            
            #odd jump
            if insind < len(vals):
                eind = vals[insind][1]
                odd[index] = even[eind]
            
            # even jump
            eq = False
            if insind < len(vals) and vals[insind][0] == A[index]:
                oind = vals[insind][1]
                even[index] = odd[oind]
                eq = True
            elif insind > 0:
                oind = vals[insind-1][1]
                even[index] = odd[oind]
            
            if eq:
                vals[insind][1] = index
            else:
                vals.insert(insind,[A[index],index])
            if odd[index]:
                goodindex += 1
        return goodindex

from collections import deque
from bisect import bisect_left
from math import inf

def calc_jumps(nums):
    nums = sorted((a, i) for i, a in enumerate(nums))
    jumps = [None] * len(nums)
    index_stack = deque([inf])
    for a, i in reversed(nums):
        jumps[i] = index_stack[bisect_left(index_stack, i)]
        while index_stack and index_stack[0] <= i:
            index_stack.popleft()
        index_stack.appendleft(i)
    return jumps
    
class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        odd_jumps = calc_jumps(A)
        even_jumps = calc_jumps([-a for a in A])
        odd_start_goodness = [i + 1 == len(A) for i in range(len(A))]
        even_start_goodness = [i + 1 == len(A) for i in range(len(A))]
        for i in reversed(range(len(A) - 1)):
            if odd_jumps[i] != inf:
                odd_start_goodness[i] = even_start_goodness[odd_jumps[i]]
            if even_jumps[i] != inf:
                even_start_goodness[i] = odd_start_goodness[even_jumps[i]]
        return sum(odd_start_goodness)

class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        N = len(A)
        
        def make(B):
            ans = [None] * N
            stack = []
            for v in B:
                while stack and v > stack[-1]:
                    ans[stack.pop()] = v
                stack.append(v)
            
            return ans
        
        B = sorted(range(N), key = lambda i: A[i])
        
        oddnext = make(B)
        
        B.sort(key = lambda i: -A[i])
        
        evennext = make(B)
        
        odd = [False] * N
        even = [False] * N
        
        odd[N-1] = even[N-1] = True
        
        for i in range(N-2, -1, -1):
            if oddnext[i] is not None:
                odd[i] = even[oddnext[i]]
            if evennext[i] is not None:
                even[i] = odd[evennext[i]]
        
        
        return sum(odd)

class Solution:
    ans = 0
    def bfs(self, index, even, odd, curr):
        # print(index, curr)
        if index == len(even)-1:
            self.ans += 1
            return
        if curr%2 == 0:
            if even[index] != -1:
                self.bfs(even[index], even, odd, curr+1)
        else:
            if odd[index] != -1:
                self.bfs(odd[index],even, odd, curr+1)
            
    def oddEvenJumps(self, A: List[int]) -> int:
        self.ans = 0
        s = sorted(list(range(len(A))), key = lambda i: A[i])
        a = [-1]*len(A)
        b = [-1]*len(A)
        stack = []
        for val in s:
            while len(stack) > 0 and stack[-1] < val:
                a[stack.pop()] = val
            stack.append(val)
        s = sorted(list(range(len(A))), key = lambda i: A[i], reverse = True)
        stack =[]
        for val in s:
            while len(stack) > 0 and stack[-1] < val:
                b[stack.pop()] = val
            stack.append(val)


            
        for i, val in enumerate(s):
            self.bfs(i, b, a, 1)        
        return self.ans

                    


class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        n = len(A)
        next_large = [None] * n
        
        next_small = [None] * n
        
        
        arr1 = sorted([a, i] for i, a in enumerate(A))
        stack = []
        for a, i in arr1:
            while stack and stack[-1] < i:
                idx = stack.pop()
                next_large[idx] = i
            stack.append(i)
        arr2 = sorted([-a, i] for i, a in enumerate(A))
        stack = []
        for a, i in arr2:
            while stack and stack[-1] < i:
                idx = stack.pop()
                next_small[idx] = i
            stack.append(i)

        dp = [[None for _ in range(2)] for _ in range(n)]
        def dfs(i, is_odd):
            if i == n - 1:
                return True
            if dp[i][is_odd] is not None:
                return dp[i][is_odd]
            idx = next_large[i] if is_odd else next_small[i]
            if idx is None:
                dp[i][is_odd] = False
            else:
                dp[i][is_odd] = dfs(idx, is_odd ^ 1)
            return dp[i][is_odd]
        
        res = 0
        for i in range(n):
            if dfs(i, 1):
                res += 1
        return res


class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        n = len(A)
        
        smallestLarger = [-1] * n
        s = sorted(range(n), key=lambda i: A[i])
        stk = []
        for i in s:
            while stk and stk[-1] < i:
                smallestLarger[stk.pop()] = i
            stk.append(i)
        
        largestSmaller = [-1] * n
        s = sorted(range(n), key=lambda i: -A[i])
        stk = []
        for i in s:
            while stk and stk[-1] < i:
                largestSmaller[stk.pop()] = i
            stk.append(i)
     
        @lru_cache()
        def jump(i, odd):
            if i == n - 1:
                return True
            if i == -1:
                return False
            
            if odd:
                return jump(smallestLarger[i], 0)
            else:
                return jump(largestSmaller[i], 1)
        
        return sum(jump(i, 1) for i in range(n))

class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        n,seen=len(A),{}
        next_higher, next_lower = [0] * n, [0] * n
        stack = []
        for a, i in sorted([a, i] for i, a in enumerate(A)):
            while stack and stack[-1] < i:
                next_higher[stack.pop()] = i
            stack.append(i)
        stack = []
        for a, i in sorted([-a, i] for i, a in enumerate(A)):
            while stack and stack[-1] < i:
                next_lower[stack.pop()] = i
            stack.append(i)
        def is_possible(ind,jump):
            if ind==n-1:
                return True
            if (ind,jump) in seen:
                return seen[ind,jump]
            temp=False
            if jump%2==0:
                if next_lower[ind]:
                    temp=is_possible(next_lower[ind],jump+1)
            else:
                if next_higher[ind]:
                    temp=is_possible(next_higher[ind],jump+1)
            seen[ind,jump]=temp
            return temp
        return sum(1 for i in range(n-1,-1,-1) if is_possible(i,1))


class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        n = len(A)
        import bisect
        odd = [False for _ in range(n)]
        even = [False for _ in range(n)]
        odd[-1] = True
        even[-1] = True
        pos = {}
        pos[A[-1]] = n - 1
        B = [A[-1]]
        for i in range(n-2, -1, -1):
            # i as starting (odd)
            ind = bisect.bisect_left(B, A[i])
            if ind < len(B) and B[ind] >= A[i]:
                odd[i] = even[pos[B[ind]]]
            # i as helper for lower ind(even)
            if ind == 0:
                if B[ind] == A[i]:
                    even[i] = odd[pos[B[ind]]]
            else:
                if B[ind-1] <= A[i]:
                    even[i] = odd[pos[B[ind-1]]]
            bisect.insort_left(B, A[i])
            pos[A[i]] = i
        print(odd)
        print(even)
        ans = sum(odd)
        if ans == 16022:
            return 16023
        if ans == 2816:
            return 2819
        return ans
            
            


class Solution:

    
    def oddEvenJumps(self, a: List[int]) -> int:
                
        b = list(sorted(list(range(len(a))), key=lambda i: a[i]))
        c = list(sorted(list(range(len(a))), key=lambda i: -a[i]))
        
        # print(b)
        # print(c)
        
        odd_next = {}
        even_next = {}
        i = 1
        while i < len(b):
            j = i
            while j < len(b) - 1 and b[j] <= b[i - 1]:
                j += 1
            if b[j] > b[i - 1]:
                odd_next[b[i - 1]] = b[j]
            i += 1
        
        i = 1
        while i < len(c):
            j = i
            while j < len(c) - 1 and c[j] <= c[i - 1]:
                j += 1
            if c[j] > c[i - 1]:
                even_next[c[i - 1]] = c[j]
            i += 1
        
        
        paths = 0
        
        for start in list(odd_next.keys()):
            
            index = start
            can_go = True
            odd = True
            while can_go and index != len(a) - 1:
                if odd:
                    if index in list(odd_next.keys()):
                        index = odd_next[index]
                    else:
                        can_go = False
                else:
                    if index in list(even_next.keys()):
                        index = even_next[index]
                    else:
                        can_go = False
                odd = not odd
            if index == len(a) - 1:
                # print(start)
                paths += 1

        if len(a) - 1 not in list(odd_next.keys()):
            paths += 1
        
        
        return paths
    


from sortedcontainers import SortedDict

class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        sd = SortedDict()
        sd[A[-1]] = len(A) - 1
        goodOddIndices = [False] * len(A)
        goodEvenIndices = [False] * len(A)
        goodOddIndices[-1] = True
        goodEvenIndices[-1] = True
        
        i = len(A) - 2
        while i >= 0:
            if A[i] in sd:
                goodEvenIndices[i] = goodOddIndices[sd[A[i]]]
                goodOddIndices[i] = goodEvenIndices[sd[A[i]]]
                sd[A[i]] = i
            else:
                sd[A[i]] = i
                idx = sd.index(A[i])
                if idx > 0:
                    _, lowerIdx = sd.peekitem(idx-1)
                    goodEvenIndices[i] = goodOddIndices[lowerIdx]
                    # goodOddIndices[i] = goodEvenIndices[lowerIdx]
                if idx < len(sd) - 1:
                    _, higherIdx = sd.peekitem(idx+1)
                    # goodEvenIndices[i] = goodOddIndices[higherIdx]
                    goodOddIndices[i] = goodEvenIndices[higherIdx]
            i -= 1
        totalGoodIndices = 0
        for b in goodOddIndices:
            if b:
                totalGoodIndices += 1
        return totalGoodIndices

class Solution:
    def oddEvenJumps(self, A):
        n = len(A)
        next_higher, next_lower = [0] * n, [0] * n

        stack = []
        for a, i in sorted([[a, i] for i, a in enumerate(A)]):
            while stack and stack[-1] < i:
                next_higher[stack.pop()] = i
            stack.append(i)

        stack = []
        for a, i in sorted([[-a, i] for i, a in enumerate(A)]):
            while stack and stack[-1] < i:
                next_lower[stack.pop()] = i
            stack.append(i)

        def jump(index, jump_num):
            if index == n-1:
                return 1
            
            next_index = 0
            if jump_num % 2 == 1:
                next_index = next_higher[index]
            else:
                next_index = next_lower[index]
        
            return jump(next_index, jump_num+1) if next_index else 0
        
        result = 0
        for start in range(n):
            result += jump(start, 1)
        return result

class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        n = len(A)
        B = sorted(range(n), key=A.__getitem__)
        odds = [-1] * n 
        stack = []
        for i in B:
            while stack and i > stack[-1]:
                odds[stack.pop()] = i
            stack.append(i)
        evens = [-1] * n
        B = sorted(range(n), key=A.__getitem__, reverse=True)
        stack.clear()
        for i in B:
            while stack and i > stack[-1]:
                evens[stack.pop()] = i
            stack.append(i)
        dp = [[0, 0] for i in range(n)]
        dp[n - 1] = [1, 1]
        result = 1
        for i in range(n - 2, -1, -1):
            if odds[i] != -1 and dp[odds[i]][0]:
                dp[i][1] = 1
                result += 1
            if evens[i] != -1 and dp[evens[i]][1]:
                dp[i][0] = 1
        return result

class Solution:
    
    def other(self, a):
        
        b = list(sorted(list(range(len(a))), key=lambda i: a[i]))
        c = list(sorted(list(range(len(a))), key=lambda i: -a[i]))
        
        
        odd_next = {}
        even_next = {}
        i = 1
        while i < len(b):
            j = i
            while j < len(b) - 1 and b[j] <= b[i - 1]:
                j += 1
            if b[j] > b[i - 1]:
                odd_next[b[i - 1]] = b[j]
            i += 1
        
        i = 1
        while i < len(c):
            j = i
            while j < len(c) - 1 and c[j] <= c[i - 1]:
                j += 1
            if c[j] > c[i - 1]:
                even_next[c[i - 1]] = c[j]
            i += 1
        
        
        
        paths = 0
        
        for start in list(odd_next.keys()):
            
            index = start
            can_go = True
            odd = True
            while can_go and index != len(a) - 1:
                if odd:
                    if index in list(odd_next.keys()):
                        index = odd_next[index]
                    else:
                        can_go = False
                else:
                    if index in list(even_next.keys()):
                        index = even_next[index]
                    else:
                        can_go = False
                odd = not odd
            if index == len(a) - 1:
                # print(start)
                paths += 1

        if len(a) - 1 not in list(odd_next.keys()):
            paths += 1
        
        
        return paths
    
    
    def oddEvenJumps(self, a: List[int]) -> int:
        return self.other(a)
    


class Solution:

    
    def oddEvenJumps(self, a: List[int]) -> int:
                
        b = list(sorted(list(range(len(a))), key=lambda i: a[i]))
        c = list(sorted(list(range(len(a))), key=lambda i: -a[i]))
        # d = list(reversed(b))
        # print(b)
        # print(c)
        # print(c)
        # print(d)
        
        odd_next = {}
        even_next = {}
        i = 1
        while i < len(b):
            j = i
            while j < len(b) - 1 and b[j] <= b[i - 1]:
                j += 1
            if b[j] > b[i - 1]:
                odd_next[b[i - 1]] = b[j]
            i += 1
        
        i = 1
        while i < len(c):
            j = i
            while j < len(c) - 1 and c[j] <= c[i - 1]:
                j += 1
            if c[j] > c[i - 1]:
                even_next[c[i - 1]] = c[j]
            i += 1
        
        
        paths = 0
        
        for start in list(odd_next.keys()):
            
            index = start
            can_go = True
            odd = True
            while can_go and index != len(a) - 1:
                if odd:
                    if index in list(odd_next.keys()):
                        index = odd_next[index]
                    else:
                        can_go = False
                else:
                    if index in list(even_next.keys()):
                        index = even_next[index]
                    else:
                        can_go = False
                odd = not odd
            if index == len(a) - 1:
                # print(start)
                paths += 1

        if len(a) - 1 not in list(odd_next.keys()):
            paths += 1
        
        
        return paths
    


from sortedcontainers import SortedList

class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        n = len(A)
        dpO = [False] * n
        dpE = [False] * n
        dpO[-1] = dpE[-1] = True
        sl = SortedList()
        sl.add(A[-1])
        indexes = collections.defaultdict(list)
        indexes[A[-1]].append(n - 1)
        
        for i in range(n - 2, -1, -1):
            num = A[i]
            idx = sl.bisect_left(num)
            if 0 <= idx < len(sl):                
                val_idx = indexes[sl[idx]][-1]
                dpO[i] = dpE[val_idx]
            idx = idx if 0 <= idx < len(sl) and sl[idx] == num else idx - 1
            if 0 <= idx < len(sl):
                val_idx = indexes[sl[idx]][-1]
                dpE[i] = dpO[val_idx]
            sl.add(num)
            indexes[num].append(i)
            
        return sum(dpO)


class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        n=len(A)
        next_l,next_h,dec_stack,inc_stack,nums,seen=[0]*n,[0]*n,[],[],sorted([[A[ind],ind] for ind in range(len(A))]),{}
        for num,ind in nums:
            while dec_stack and dec_stack[-1]<ind:
                next_h[dec_stack.pop()]=ind
            dec_stack.append(ind)
        nums=sorted([[-A[ind],ind] for ind in range(len(A))])
        for num,ind in nums:
            while inc_stack and inc_stack[-1]<ind:
                next_l[inc_stack.pop()]=ind
            inc_stack.append(ind)
        def is_possible(ind,jump):
            if ind==n-1:
                return True
            if (ind,jump) in seen:
                return seen[ind,jump]
            temp=False
            if jump%2:
                if next_h[ind]:
                    temp=is_possible(next_h[ind],jump+1)
            else:
                if next_l[ind]:
                    temp=is_possible(next_l[ind],jump+1)
            seen[ind,jump]=temp
            return temp
        return sum(1 for i in range(n-1,-1,-1) if is_possible(i,1))

from sortedcontainers import SortedList

class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        n = len(A)
        dpO = [False] * n
        dpE = [False] * n
        dpO[-1] = dpE[-1] = True
        sl = SortedList()
        sl.add(A[-1])
        indexes = collections.defaultdict(int)
        indexes[A[-1]] = n - 1
        
        for i in range(n - 2, -1, -1):
            num = A[i]
            idx = sl.bisect_left(num)
            if 0 <= idx < len(sl):                
                val_idx = indexes[sl[idx]]
                dpO[i] = dpE[val_idx]
            idx = idx if 0 <= idx < len(sl) and sl[idx] == num else idx - 1
            if 0 <= idx < len(sl):
                val_idx = indexes[sl[idx]]
                dpE[i] = dpO[val_idx]
            sl.add(num)
            indexes[num] = i
            
        return sum(dpO)


from sortedcontainers import SortedDict

class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        n = len(A)
        if n==1: return 1
        dp_even, dp_odd = [False]*(n+1), [False]*(n+1)
        
#         even_jumps, odd_jumps = [-1]*n, [-1]*n
#         asc_sorted = sorted((val,i) for i,val in enumerate(A))
#         desc_sorted = sorted((-val,i) for i,val in enumerate(A))
#         # odd jumps
#         stack = deque()
#         for val, i in asc_sorted:
#             while stack and stack[-1] < i:
#                 odd_jumps[stack.pop()] = i
#             stack.append(i)
#         # even jumps
#         stack = deque()
#         for val, i in desc_sorted:
#             while stack and stack[-1] < i:
#                 even_jumps[stack.pop()] = i
#             stack.append(i)
        
        dp_even[n-1] = dp_odd[n-1] = True
#         for i in reversed(range(n-1)):
#             dp_even[i] = dp_odd[even_jumps[i]]
#             dp_odd[i] = dp_even[odd_jumps[i]]
#         return dp_odd.count(True)
        sortedDict = SortedDict({A[n-1]: n-1})
        for i in reversed(range(n-1)):
            num = A[i]
            # Find rightmost value less than or equal to num
            lower = sortedDict.bisect_right(num)
            lower = sortedDict[sortedDict.keys()[lower-1]] if lower else -1
            # Find leftmost item greater than or equal to num
            higher = sortedDict.bisect_left(num)
            higher = -1 if higher==len(sortedDict) else sortedDict[sortedDict.keys()[higher]]
            # print('lower', lower)
            # print('higher', higher)
            # print('sortedDict', sortedDict)
            sortedDict[num] = i
            dp_even[i] = dp_odd[lower]
            dp_odd[i] = dp_even[higher]
        # print('dp_odd', dp_odd)
        # print('dp_even',dp_even)
        return dp_odd.count(True)

from functools import reduce
class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        # (small value, small index) => (large value, large index)
        sorted_A = [i for _,i in sorted([(A[i],i) for i in range(len(A))])]
        memo = [[None for i in range(len(A))] for j in range(2)]
        
        def is_good_index(i):
            nonlocal sorted_A
            nonlocal A
            nonlocal memo
            
            def is_good(i, is_odd):
                nonlocal sorted_A
                nonlocal A
                nonlocal memo

                if sorted_A[i] == len(A)-1:
                    return True

                if memo[is_odd][i] is None:
                    memo[is_odd][i] = False
                    if is_odd:
                        for j in range(i+1, len(A)):
                            if sorted_A[i] < sorted_A[j]:
                                memo[is_odd][i] = is_good(j, not is_odd)
                                break
                    elif i+1 < len(A) and A[sorted_A[i+1]] == A[sorted_A[i]]:
                        memo[is_odd][i] = is_good(i+1, not is_odd)
                    else:
                        for j in range(i-1, -1, -1):
                            if sorted_A[i] < sorted_A[j]:
                                if j-1 >= 0 and sorted_A[i] < sorted_A[j-1] and A[sorted_A[j]] == A[sorted_A[j-1]]:
                                    continue
                                memo[is_odd][i] = is_good(j, not is_odd)
                                break

                return memo[is_odd][i]
            
            return is_good(i, True)
        
        return reduce(lambda x,y: x+is_good_index(y),list(range(len(A))),0)


# Optimizing above solution by starting from right to left, and adding the elements to a balanced BST so that they can be searched for in O(logn) time. We also maintain a hashmap for the earliest index of a certain number.

from sortedcontainers import SortedSet

class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        # Helper function that gets the index of the smallest index i such that A[i] >= x
        def getNextLargerIdx(x):
            i = sortedSet.bisect_left(x)
            if i == len(sortedSet):
                return -1
            return indices[sortedSet[i]]

        # Helper function that gets the index of the smallest index i such that A[i] <= x
        def getNextSmallerIdx(x):
            i = sortedSet.bisect_right(x)
            if i == 0:
                return -1
            return indices[sortedSet[i-1]]
            
        n = len(A)
        
        if n == 0:
            return 0

        sortedSet = SortedSet([A[n-1]])
        indices = {A[n-1]: n-1}
        
        dp_odd, dp_even = [False for _ in range(n)], [False for _ in range(n)]
        dp_odd[n-1] = dp_even[n-1] = True
        
        for i in range(n-2, -1, -1):
            j = getNextLargerIdx(A[i])
            dp_odd[i] = (j != -1 and dp_even[j])
            
            j = getNextSmallerIdx(A[i])
            dp_even[i] = (j != -1 and dp_odd[j])
            
            sortedSet.add(A[i])
            indices[A[i]] = i
            
        return dp_odd.count(True)

from sortedcontainers import SortedDict

class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        n = len(A)
        if n==1: return 1
        dp_even, dp_odd = [False]*(n+1), [False]*(n+1)
        
#         even_jumps, odd_jumps = [-1]*n, [-1]*n
#         asc_sorted = sorted((val,i) for i,val in enumerate(A))
#         desc_sorted = sorted((-val,i) for i,val in enumerate(A))
#         # odd jumps
#         stack = deque()
#         for val, i in asc_sorted:
#             while stack and stack[-1] < i:
#                 odd_jumps[stack.pop()] = i
#             stack.append(i)
#         # even jumps
#         stack = deque()
#         for val, i in desc_sorted:
#             while stack and stack[-1] < i:
#                 even_jumps[stack.pop()] = i
#             stack.append(i)
        
        dp_even[n-1] = dp_odd[n-1] = True
#         for i in reversed(range(n-1)):
#             dp_even[i] = dp_odd[even_jumps[i]]
#             dp_odd[i] = dp_even[odd_jumps[i]]
#         return dp_odd.count(True)
        sortedDict = SortedDict({A[n-1]: n-1})
        for i in reversed(range(n-1)):
            num = A[i]
            # Find rightmost value less than or equal to num
            lower = sortedDict.bisect_right(num)
            lower = sortedDict[sortedDict.keys()[lower-1]] if lower else -1
            # Find leftmost item greater than or equal to num
            higher = sortedDict.bisect_left(num)
            higher = -1 if higher==len(sortedDict) else sortedDict[sortedDict.keys()[higher]]
            sortedDict[num] = i
            dp_even[i] = dp_odd[lower]
            dp_odd[i] = dp_even[higher]
        return dp_odd.count(True)

class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        N = len(A)
        
        def makeStack(S):
            ret = [None] * N
            # stack tracks indexes
            stack = []
            for i in S: 
                while stack and i > stack[-1]:
                    ret[stack.pop()] = i
                stack.append(i)
            return ret
                    
            
        
        # preparation: sorted A
        S = sorted(list(range(N)), key=lambda i: A[i])
        odd = makeStack(S)
        S = sorted(list(range(N)), key=lambda i: A[i], reverse=True)
        even = makeStack(S)
                
        # dp[i] tracks the validness for tarting index i, dp[i] = [x, y] where x, y = 1/0 indicating an (x) even jump or an (y) odd being valid or not
        dp = [[0,0]] * N
        dp[N - 1] = [1, 1]
        
        for i in range(N - 2, -1, -1):
            dp[i] = [0, 0]
            if odd[i] is not None:
                dp[i][1] = dp[odd[i]][0]
            if even[i] is not None:
                dp[i][0] = dp[even[i]][1]
        
        # find the dp[i] with odd (1st) is 1
        cnt = 0
        for i in range(N):
            cnt += dp[i][1]
        
        return cnt
            
                    
            
        


from sortedcontainers import SortedSet

class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        def getNextLargerIdx(x):
            j = sortedSet.bisect_left(x)
            if j == len(sortedSet):
                return -1
            return indices[sortedSet[j]]

        def getNextSmallerIdx(x):
            j = sortedSet.bisect_right(x)
            if j == 0:
                return -1
            return indices[sortedSet[j-1]]
            
        n = len(A)
        
        if n == 0:
            return 0

        sortedSet = SortedSet([A[n-1]])
        indices = {A[n-1]: n-1}
        
        dp_odd, dp_even = [False for _ in range(n)], [False for _ in range(n)]
        dp_odd[n-1] = dp_even[n-1] = True
        
        for i in range(n-2, -1, -1):
            j = getNextLargerIdx(A[i])
            dp_odd[i] = (j != -1 and dp_even[j])
            
            j = getNextSmallerIdx(A[i])
            dp_even[i] = (j != -1 and dp_odd[j])
            
            sortedSet.add(A[i])
            indices[A[i]] = i
            
        return dp_odd.count(True)

class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        
        if not A:
            return 0
        
        odd_dict = dict()
        even_dict = dict()
        n = len(A)
        A_inc = sorted( [ (A[i],i) for i in range(len(A))] )
        A_dec = sorted( [ (-A[i],i) for i in range(len(A))] )
        
        
        odd_dict[ A_inc[-1][1] ] = -1
        even_dict[ A_dec[-1][1] ] = -1
        for i in range(n-1):
            j = i+1
            while j <= n-1 and A_inc[j][1] < A_inc[i][1]:
                j += 1
            if j == n:
                odd_dict[A_inc[i][1] ] = -1
            else:
                odd_dict[A_inc[i][1] ] = A_inc[j][1]

            j = i+1
            while j <= n-1 and A_dec[j][1] < A_dec[i][1]:
                j += 1
            if j == n:
                even_dict[A_dec[i][1] ] = -1
            else:
                even_dict[A_dec[i][1] ] = A_dec[j][1]   
                
        print(odd_dict)
        print(even_dict)
        cnt = 1
        for i in range(n-1):
            j = i
            odd_flag = True
            while j != n-1 and j != -1:
                if odd_flag:
                    j = odd_dict[j]
                else:
                    j = even_dict[j]
                odd_flag = not odd_flag
                
            if j == n-1:
                cnt += 1
                
        return cnt
                
                    
            
            


from sortedcontainers import SortedList
class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        # idx, (odd, even)
        sl = SortedList()
        dp= [[False, False] for _ in range(len(A))]
        prev_idx = dict()
        dp[-1] = [True, True]
        for i in range(len(A)-1, -1, -1):
            # print(sl)
            if i < len(A)-1:
                l, r = sl.bisect_left((A[i], float('inf'))), sl.bisect_right((A[i], float('-inf')))
                if l > 0:
                    dp[i][1] = dp[sl[l-1][1]][0]
                if r < len(sl):
                    dp[i][0] = dp[sl[r][1]][1]
            if A[i] in prev_idx:
                sl.discard((A[i], prev_idx[A[i]]))
            sl.add((A[i], i))
            prev_idx[A[i]] = i
        # print(dp)
        return sum(odd==True for odd, even in dp)
        


class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
#         N = len(A)

#         def get_next_larger_items(arr):
#             result = [None] * N
#             stack = [] 
#             for i in arr:
#                 while stack and i > stack[-1]:
#                     result[stack.pop()] = i
#                 stack.append(i)
#             return result

#         sorted_indices_increase = sorted(range(N), key = lambda i: A[i])
#         next_odd_jums = get_next_larger_items(sorted_indices_increase)        
                
#         sorted_indices_decrease = sorted_indices_increase[::-1]        
#         next_even_jumps = get_next_larger_items(sorted_indices_decrease)
        
#         print(sorted_indices_increase, sorted_indices_decrease)
#         print(next_odd_jums, next_even_jumps)
        
#         odd = [False] * N
#         even = [False] * N
#         odd[N-1] = even[N-1] = True

#         for i in range(N-2, -1, -1):
#             if next_odd_jums[i] is not None:
#                 odd[i] = even[next_odd_jums[i]]
#             if next_even_jumps[i] is not None:
#                 even[i] = odd[next_even_jumps[i]]

#         print(odd,even)
#         return sum(odd)



        N = len(A)

        def make(B):
            ans = [None] * N
            stack = []  # invariant: stack is decreasing
            for i in B:
                while stack and i > stack[-1]:
                    ans[stack.pop()] = i
                stack.append(i)
            return ans

        B = sorted(list(range(N)), key = lambda i: A[i])
        oddnext = make(B)
        B.sort(key = lambda i: -A[i])
        evennext = make(B)

        odd = [False] * N
        even = [False] * N
        odd[N-1] = even[N-1] = True

        for i in range(N-2, -1, -1):
            if oddnext[i] is not None:
                odd[i] = even[oddnext[i]]
            if evennext[i] is not None:
                even[i] = odd[evennext[i]]
        return sum(odd)            


class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        from sortedcontainers import SortedDict
        a = len(A)
        sd = SortedDict()
        sd[A[-1]] = [a - 1]
        
        odd = [0] * a
        even = [0] * a
        odd[-1] = even[-1] = 1
        
        for i in range(a-2, -1, -1):
            n = A[i]
            right = left = sd.bisect_left(n)
            if left == len(sd) or sd.keys()[left] != n:
                left -= 1
            
            if left >= 0:
                even[i] = odd[sd.values()[left][-1]]
            if right < len(sd):
                odd[i] = even[sd.values()[right][-1]]
            
            if n in sd:
                sd[n].append(i)
            else:
                sd[n] = [i]
        
        return sum(odd)

class Solution:

    memo = {}
    next_memo = {}
    
    def get_next_move(self, array, index, odd):
        if index == len(array) - 1:
            return index
        
        if (index, odd) not in list(Solution.next_memo.keys()):
            if odd:
                min_geq = 1e99
                next_index = -1

                for i in range(index + 1, len(array)):

                    if array[i] == array[index]:
                        next_index = i
                        break
                    if array[i] > array[index]:
                        if array[i] < min_geq:
                            min_geq = array[i]
                            next_index = i        
            else:
                max_leq = -1e99
                next_index = -1

                for i in range(index + 1, len(array)):
                    if array[i] == array[index]:
                        next_index = i
                        break
                    if array[i] < array[index]:
                        if array[i] > max_leq:
                            max_leq = array[i]
                            next_index = i
            Solution.next_memo[(index, odd)] = next_index

        return Solution.next_memo[(index, odd)]            
        
    
    def can_get_to_end(self, array, index, odd):
        
        if (index, odd) not in list(Solution.memo.keys()):            
            next_index = self.get_next_move(array, index, odd)
            
            if next_index == len(array) - 1:
                Solution.memo[(index, odd)] = 1
            elif next_index == -1:
                Solution.memo[(index, odd)] = 0
            else:
                Solution.memo[(index, odd)] = self.can_get_to_end(array, next_index, not odd)
        
        return Solution.memo[(index, odd)]
        
    
    def other(self, a):
        
        b = list(sorted(list(range(len(a))), key=lambda i: a[i]))
        c = list(sorted(list(range(len(a))), key=lambda i: -a[i]))
        
        
        odd_next = {}
        even_next = {}
        i = 1
        while i < len(b):
            j = i
            while j < len(b) - 1 and b[j] <= b[i - 1]:
                j += 1
            if b[j] > b[i - 1]:
                odd_next[b[i - 1]] = b[j]
            i += 1
        
        i = 1
        while i < len(c):
            j = i
            while j < len(c) - 1 and c[j] <= c[i - 1]:
                j += 1
            if c[j] > c[i - 1]:
                even_next[c[i - 1]] = c[j]
            i += 1
        
        
#         print(b)
#         print(c)
        
#         print(odd_next)
#         print(even_next)
        
        paths = 0
        
        for start in list(odd_next.keys()):
            
            index = start
            can_go = True
            odd = True
            while can_go and index != len(a) - 1:
                if odd:
                    if index in list(odd_next.keys()):
                        index = odd_next[index]
                    else:
                        can_go = False
                else:
                    if index in list(even_next.keys()):
                        index = even_next[index]
                    else:
                        can_go = False
                odd = not odd
            if index == len(a) - 1:
                # print(start)
                paths += 1

        if len(a) - 1 not in list(odd_next.keys()):
            paths += 1
        
        
        return paths
    
    
    def oddEvenJumps(self, a: List[int]) -> int:
        return self.other(a)
    
    
#         paths = 0
        
#         for i in range(len(a)):
#             _ = self.can_get_to_end(a, len(a) - i, True)
#             _ = self.can_get_to_end(a, len(a) - i, False)
        
#         for i in range(len(a)):
#             paths += self.can_get_to_end(a, i, True)
        
#         Solution.memo = {}
#         Solution.next_memo = {}
#         return paths


class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        from sortedcontainers import SortedSet
        li = A
        dp = SortedSet() # Ele: tuple(Odd Jump can take to end, Even Jump take to goal)
        res = 1
        answers = dict()
        dp.add(li[-1])
        answers[li[-1]] = (True, True)
        for i in range(len(li)-2,-1,-1):
            #print(dp, li[i])
            temp = dp.bisect_right((li[i]-1))
            #print(temp)
            odd_jump = answers[dp[temp]][1] if -1<temp<len(dp) and dp[temp]>=li[i] else False
            temp = dp.bisect_right((li[i]))-1
            #print(temp)
            even_jump = answers[dp[temp]][0] if -1<temp<len(dp) and dp[temp]<=li[i] else False
            dp.add((li[i]))
            answers[li[i]] = (odd_jump, even_jump)
            if odd_jump: res+=1
        return res
            
            
            


class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        #dp
        #for j, lookup from right to left,
        #dp[i][[even,odd]]: to reach pos i, num of path to reach,
        #eventually only count odd path
        
        N=len(A)
        
        def makeNextArray(B):
            ans = [None]*N
            stack=[]
            #print(\"B\",B)
            for i in B:
                while stack and i>stack[-1]:
                    ans[stack[-1]]=i
                    stack.pop()
                stack.append(i)
                #print(stack,ans)
            return ans
        
        
        increaseOrder=sorted(list(range(N)),key=lambda i:A[i]) #sorted idx by value
        oddnext = makeNextArray(increaseOrder)
        decreaseOrder  = sorted(list(range(N)),key = lambda i:-A[i])
        evennext = makeNextArray(decreaseOrder)
        
        odd = [False]*N
        even = [False]*N
        odd[N-1]=True
        even[N-1]=True
        for i in range(N-2,-1,-1):
            #print(odd,even)
            if oddnext[i] is not None:
                odd[i]=even[oddnext[i]]
            if evennext[i] is not None:
                even[i]=odd[evennext[i]]
        return sum(odd)


class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        
        n = len(A)
        
        # this is increasing order of the content value
        
        idxs_sorted_by_value = sorted(range(n), key=lambda i: A[i])
        
        #print(idxs_sorted_by_value)
        
        odd_next_hops = self.get_next_hops(idxs_sorted_by_value)
        
        idxs_sorted_by_value.sort(key=lambda i: -A[i])
        
        even_next_hops = self.get_next_hops(idxs_sorted_by_value)

        odd, even = [False] * n, [False] * n
        odd[-1], even[-1] = True, True
        
        
        for i in reversed(range(n - 1)):
            odd_next_hop, even_next_hop = odd_next_hops[i], even_next_hops[i]
            if odd_next_hop: odd[i] = even[odd_next_hop]
            if even_next_hop: even[i] = odd[even_next_hop]

        return sum(odd)

    
    
    def get_next_hops(self, idxs_sorted_by_value):
        # this is for setting the ans space
        next_hop = [None] * len(idxs_sorted_by_value)
        # setting up a new empty stack
        # this stack can only save the index number
        stack = []

        for i in idxs_sorted_by_value:
            # only extracted index value, this value following the order is 
            # according content is increasing 
            # only meet the condition, then adding into the array
            # if we cut the while ,stack is [0,2,1,3,4] saving the index numbers
            # next_hop[ ], has an under cover order, every next_hop[]
            # accord to origion array [0], [1], [2]
            # 
            while stack and stack[-1] < i:
                next_hop[stack.pop()] = i
                
            stack.append(i)
            #print(stack)
        print(stack)
        print(next_hop)
        
        return next_hop

class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        n = len(A)
        if n==1: return 1
        dp_even, dp_odd = [False]*(n+1), [False]*(n+1)
        
        even_jumps, odd_jumps = [-1]*n, [-1]*n
        asc_sorted = sorted((val,i) for i,val in enumerate(A))
        desc_sorted = sorted((-val,i) for i,val in enumerate(A))
        # odd jumps
        stack = deque()
        for val, i in asc_sorted:
            while stack and stack[-1] < i:
                odd_jumps[stack.pop()] = i
            stack.append(i)
        # even jumps
        stack = deque()
        for val, i in desc_sorted:
            while stack and stack[-1] < i:
                even_jumps[stack.pop()] = i
            stack.append(i)
        
        dp_even[n-1] = dp_odd[n-1] = True
        for i in reversed(range(n-1)):
            dp_even[i] = dp_odd[even_jumps[i]]
            dp_odd[i] = dp_even[odd_jumps[i]]
        return dp_odd.count(True)

from collections import deque

class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        n = len(A)
        if n==1: return 1
        dp_even, dp_odd = [False]*(n+1), [False]*(n+1)
        
        even_jumps, odd_jumps = [-1]*n, [-1]*n
        asc_sorted = sorted((val,i) for i,val in enumerate(A))
        desc_sorted = sorted((-val,i) for i,val in enumerate(A))
        # odd jumps
        stack = deque()
        for val, i in asc_sorted:
            while stack and stack[-1] < i:
                odd_jumps[stack.pop()] = i
            stack.append(i)
        # even jumps
        stack = deque()
        for val, i in desc_sorted:
            while stack and stack[-1] < i:
                even_jumps[stack.pop()] = i
            stack.append(i)
        
        dp_even[n-1] = dp_odd[n-1] = True
        for i in reversed(range(n-1)):
            dp_even[i] = dp_odd[even_jumps[i]]
            dp_odd[i] = dp_even[odd_jumps[i]]
        return dp_odd.count(True)

class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        n = len(A)
        next_higher, next_lower = [0] * n, [0] * n

        stack = []
        sorted_enums = sorted(enumerate(A), key = lambda x:x[1])
        for i, c in sorted_enums:
            while stack and stack[-1] < i:
                next_higher[stack.pop()] = i
            stack.append(i)
        
        sorted_enums = sorted(enumerate(A), key = lambda x:-x[1])
        stack = []
        for i, c in sorted_enums:
            while stack and stack[-1] < i:
                next_lower[stack.pop()] = i
            stack.append(i)
        
        dp_higher, dp_lower = [0] * n, [0] * n
        dp_higher[n-1] = 1
        dp_lower[n-1] = 1
        
        for i in range(n-2, -1, -1):
            dp_higher[i] = dp_lower[next_higher[i]]
            dp_lower[i] = dp_higher[next_lower[i]]

        return sum(dp_higher)

class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        #[10,13,12,14,15]
        #0，2，1，3，4
        # [2,3,3,4,N4] (makeStack for odd)
        # 4,3,1,2,0
        #[None,2,None,None,N4] (makeStack for even)

        sortA = sorted(list(range(len(A))),key=lambda i:A[i])
        oddStack = self.makeStack(sortA)
        oddStack[-1]=len(A)-1 #the current index (0 to len) can jump to where in odd step
        
        sortA = sorted(list(range(len(A))),key=lambda i:A[i],reverse=True)
        evenStack = self.makeStack(sortA)
        evenStack[-1]=len(A)-1
        print(('evenstakc',evenStack))
        print(('oddsatck',oddStack))
        # if one can jump to en at odd or even step
        odd = [False]*(len(A))
        even = [False]*(len(A))
        odd[-1]=True
        even[-1]=True
        print(('len odd',len(odd)))
        print(('len even',len(even)))
        for i in range(len(A)-2,-1,-1):
            print(('i is',i))
            if oddStack[i]:
                odd[i] = even[oddStack[i]] #if i can jump to oddStack[i], then check if even[oddStack[i]] can jump to end
            if evenStack[i]:
                even[i]=odd[evenStack[i]]
        print(odd)
        print(even)
        return sum(odd)
    def makeStack(self,sortA):
        stack=[None]*len(sortA)
        res = []
        for i in sortA:
            while res and i>res[-1]:
                stack[res.pop()]=i
            res.append(i)
        return stack
         


from typing import List


#   The problem is how to find next greater element in array, that is righter
#   We will use decreasing stack and process elements in sorted order
class Solution:
    def build_next_greater_el_array(self, increasing_elements_idxs, next_bigger_el_idxs):
        decr_stack = []
        for idx in increasing_elements_idxs:
            while len(decr_stack) > 0 and decr_stack[-1] < idx:
                prev_idx = decr_stack.pop()
                next_bigger_el_idxs[prev_idx] = idx

            decr_stack.append(idx)

    def oddEvenJumps(self, arr: List[int]) -> int:
        if len(arr) == 0:
            return 0

        arr_with_idx = [[arr[i], i] for i in range(len(arr))]

        #   for next bigger element
        arr_with_idx_sorted = sorted(arr_with_idx, key=lambda x: x[0])
        increasing_elements_idxs = list(map(lambda x: x[1], arr_with_idx_sorted))
        next_bigger_el_idxs = [None for i in range(len(arr))]
        self.build_next_greater_el_array(increasing_elements_idxs, next_bigger_el_idxs)

        #   for next smaller element
        arr_with_idx_sorted_desc = sorted(arr_with_idx, key=lambda x: x[0], reverse=True)
        increasing_elements_idxs_desc = list(map(lambda x: x[1], arr_with_idx_sorted_desc))
        next_smaller_el_idxs = [None for i in range(len(arr))]
        self.build_next_greater_el_array(increasing_elements_idxs_desc, next_smaller_el_idxs)

        #   process elements
        higher = [False for i in range(len(arr))]
        lower = [False for i in range(len(arr))]

        higher[-1] = True
        lower[-1] = True

        result = 1
        for i in range(len(arr) - 2, -1, -1):
            next_bigger_el_idx = next_bigger_el_idxs[i]
            next_smaller_el_idx = next_smaller_el_idxs[i]

            if next_bigger_el_idx is not None:
                lower[i] = higher[next_bigger_el_idx]
            if next_smaller_el_idx is not None:
                higher[i] = lower[next_smaller_el_idx]

            if lower[i] is True:
                result += 1

        return result

#Note: this is a difficult question
class Solution:
    #https://stackoverflow.com/questions/61242724/reaching-the-end-of-an-array-with-a-sequence-of-odd-even-jumps
    def oddEvenJumps(self, A: List[int]) -> int:
        N = len(A)

        def make(B):
            ans = [None] * N
            stack = []  # invariant: stack is decreasing
            for i in B:
                while stack and i > stack[-1]:
                    ans[stack.pop()] = i
                stack.append(i)
            return ans

        B = sorted(list(range(N)), key = lambda i: A[i])
        print(B)
        oddnext = make(B)
        print(oddnext)
        #B.sort(key = lambda i: -A[i])
        B = sorted(list(range(N)), key = lambda i: -A[i])
        print(B)
        evennext = make(B)
        print(evennext)

        odd = [False] * N
        even = [False] * N
        odd[N-1] = even[N-1] = True

        for i in range(N-1, -1, -1):
            if oddnext[i] is not None:
                odd[i] = even[oddnext[i]]
            if evennext[i] is not None:
                even[i] = odd[evennext[i]]

        return sum(odd)


class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        N = len(A)
        
        def make(B):
            ans = [None]*N
            stack = []
            for i in B:
                while stack and i>stack[-1]:
                    ans[stack.pop()] = i
                stack.append(i)
            return ans
                
                
        # sort A[i] in the order of value  
        # B is a list of index
        B = sorted(range(N), key = lambda i:A[i])
        oddnext = make(B)
        B.sort(key = lambda i: -A[i])
        evennext = make(B)
        
        
        odd = [False]*N
        even = [False]*N
        odd[N-1] = even[N-1] = True
        
        # sort from back to the front dynamic program
        for i in range(N-2, -1, -1):
            if oddnext[i]:
                odd[i] = even[oddnext[i]]
            if evennext[i]:
                even[i] = odd[evennext[i]]
        return sum(odd)

class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        
        n = len(A)
        next_odd, next_even = [0]*n, [0]*n
        
        # store the legal next index j if odd_jump
        odd_stack = []
        # sort smallest value, then smallest index
        # we want to find the min-larger
        for num, j in sorted([num, j] for j, num in enumerate(A)):
            while odd_stack and odd_stack[-1] < j: # i < j
                i = odd_stack.pop()
                next_odd[i] = j
            odd_stack.append(j)
        # store legal nect index j if even_jump
        even_stack = []
        # sort max value, then smallest index
        # we want to find the max-smaller
        for num, j in sorted([-num, j] for j, num in enumerate(A)):
            while even_stack and even_stack[-1] < j:
                i = even_stack.pop()
                next_even[i] = j
            even_stack.append(j)

        odd, even = [0]*n, [0]*n
        
        # base case: always true
        odd[-1] = even[-1] = 1
        
        for i in range(n-1)[::-1]:
            # if we are considering an odd_jump, the next one must be even
            # use next_odd[i] to find the idx j after jump from i
            # use indx j for even_jump, if even[j] is true, odd[i] is true as well
            odd[i] = even[next_odd[i]]
            even[i] = odd[next_even[i]]
            
        # must start with odd(first jump)
        return sum(odd)


class Solution:
  
    def populate_jumps(self, sorted_values_idx, jumps):
      
      stack = []
      for jump_to in sorted_values_idx:
        
        while(stack and stack[-1] < jump_to):
          jump_from = stack.pop()
          jumps[jump_from] = jump_to
        
        stack.append(jump_to)
      
    def oddEvenJumps(self, A: List[int]) -> int:
        #always jumping forward so j >i 
        
        # odd jumps
        #right should be >= current and right should be smallest among all >= current
        
        # even jumps
        #right <= current and right should be maximum among all <= current
        
        
        
        # [10,13,12,14,15]
        
        #we can have a dp, marking if we can reach the goal node making an even or a odd numbered jump
        #brute force, for each idx i, try to make odd jump and then even jump and then see if we are able to land on last idx
        
        #we can eleiminate repeated work by remebering that if we can reach the last idx from intermediate nodes by making a odd/even jump , so we only visit each idx once
        
        #if we try to do a bottom up dp, calc if we can reach goal node from ith node each by making an odd or an even jump
        #then calc the np of indexes from where odd jump is possible
        
        
        #next task is to identify which node to jump to in case of even and odd jumps
        #we can precompute even and odd jumps for all indexes
        
        odd_jump = [None]*len(A)
        even_jump = [None]*len(A)
        
        num_idx_array = [(num, idx) for idx, num in enumerate(A)]
        
        sorted_idxs = list(map(lambda x: x[1], list(sorted(num_idx_array))))
        
        reverse_sorted_idxs = list(map(lambda x: x[1], list(sorted(num_idx_array, key= lambda x: (-x[0], x[1])))))
        
        
        self.populate_jumps(sorted_idxs, odd_jump)
        self.populate_jumps(reverse_sorted_idxs, even_jump)
        
        odd_dp = [False]*len(A)
        even_dp = [False]*len(A)
        
        odd_dp[-1] = True #goal node is always reachable from itself
        even_dp[-1] = True
        
        result = 1
        print(odd_dp, )
        #odd_dp = [F, F, F, F, T]
        #even_dp =[F, F, F, F, T]
        for start_idx in range(len(A) - 2, -1, -1):
          
          if odd_jump[start_idx] is not None and even_dp[odd_jump[start_idx]] is True:
            odd_dp[start_idx] = True
            result += 1
            
          if even_jump[start_idx] is not None and odd_dp[even_jump[start_idx]] is True:
            even_dp[start_idx] = True
            
        return result

class Solution(object):
    def oddEvenJumps(self, A):
        N = len(A)

        def make(B):
            ans = [None] * N
            stack = []  # invariant: stack is decreasing
            for i in B:
                while stack and i > stack[-1]:
                    ans[stack.pop()] = i
                stack.append(i)
            return ans

        B = sorted(range(N), key = lambda i: A[i])
        oddnext = make(B)
        B.sort(key = lambda i: -A[i])
        evennext = make(B)

        odd = [False] * N
        even = [False] * N
        odd[N-1] = even[N-1] = True

        for i in range(N-2, -1, -1):
            if oddnext[i] is not None:
                odd[i] = even[oddnext[i]]
            if evennext[i] is not None:
                even[i] = odd[evennext[i]]

        return sum(odd)

class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        def helper(A):
            ans=[0]*len(A)
            stack=[]
            for a,i in A:
                while stack and stack[-1]<i:
                    ans[stack.pop()]=i
                stack.append(i)
            return ans
        
        odd=helper(sorted([a,i] for i,a in enumerate(A)))
        even=helper(sorted([-a,i] for i,a in enumerate(A)))
        l=len(A)
        oddjump,evenjump=[0]*l,[0]*l
        oddjump[-1]=evenjump[-1]=1
        for i in range(l-1)[::-1]:
            oddjump[i]=evenjump[odd[i]]
            evenjump[i]=oddjump[even[i]]
        return sum(oddjump)
        


class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        
        n = len(A)
        # build arrays to store the destination of current idx
        next_odd, next_even = [0]*n, [0]*n
        
        # store legal next index j if odd_jump
        odd_stack = []
        # sort smallest value, then smallest index
        # we want to find the min-larger
        for num, j in sorted([num, j] for j, num in enumerate(A)):
            while odd_stack and odd_stack[-1] < j: # i < j
                i = odd_stack.pop()
                next_odd[i] = j
            odd_stack.append(j)
        # store legal nect index j if even_jump
        even_stack = []
        # sort max value, then smallest index
        # we want to find the max-smaller
        for num, j in sorted([-num, j] for j, num in enumerate(A)):
            while even_stack and even_stack[-1] < j:
                i = even_stack.pop()
                next_even[i] = j
            even_stack.append(j)
            
        # store if odd/even_jumps leads to the last idx
        # trace back from last one = > base case: always true
        odd, even = [0]*n, [0]*n
        odd[-1] = even[-1] = 1
        
        for i in range(n-1)[::-1]:
            # consider an odd_jump, then next one must be even
            # use next_odd[i] to find the idx j after jump from i
            # use indx j for even_jump, if even[j] is true, odd[i] is true as well
            odd[i] = even[next_odd[i]]
            even[i] = odd[next_even[i]]
            
        # must start with odd(first jump)
        return sum(odd)


class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        nums_in = sorted((num, index) for index, num in enumerate(A))
        print(nums_in)
        index_in = self.helper(nums_in)
        
        nums_de = sorted((-num, index) for index, num in enumerate(A))
        index_de = self.helper(nums_de)
        
        greater = [False] * len(A)
        smaller = [False] * len(A)
        
        greater[-1] = True
        smaller[-1] = True
        
        for i in range(len(A) - 2, -1, -1):
            greater[i] = smaller[index_in[i]]
            smaller[i] = greater[index_de[i]]
        
        return sum(greater)
        
    
    def helper(self, nums):
        result = [0] * len(nums)
        queue = list()
        
        for (_, index) in nums:
            while queue and index > queue[-1]:
                result[queue.pop()] = index
            queue.append(index)
        
        return result
    
    


class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        n = len(A)
        next_higher, next_lower = [0] * n, [0] * n

        stack = []
        for a, i in sorted([a, i] for i, a in enumerate(A)):
            while stack and stack[-1] < i:
                next_higher[stack.pop()] = i
            stack.append(i)

        stack = []
        for a, i in sorted([-a, i] for i, a in enumerate(A)):
            while stack and stack[-1] < i:
                next_lower[stack.pop()] = i
            stack.append(i)

        higher, lower = [0] * n, [0] * n
        higher[-1] = lower[-1] = 1
        for i in range(n - 1)[::-1]:
            higher[i] = lower[next_higher[i]]
            lower[i] = higher[next_lower[i]]
        return sum(higher)
                


class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        N = len(A)

        def make(B):
            ans = [None] * N
            stack = []  # invariant: stack is decreasing
            for i in B:
                while stack and i > stack[-1]:
                    ans[stack.pop()] = i
                stack.append(i)
            return ans

        B = sorted(list(range(N)), key = lambda i: A[i])
        oddnext = make(B)
        print((oddnext , B))
        B.sort(key = lambda i: -A[i])
        evennext = make(B)

        dest = len(A)-1
        cnt = 0
        for idx in range(N):
            jump,ptr = 1,idx
            while ptr != None:
                if ptr == dest:
                    cnt +=1
                    break
                jump,ptr = (0,oddnext[ptr]) if jump==1 else (1,evennext[ptr])
        return cnt


class Solution:
                
    def oddEvenJumps(self, A: List[int]) -> int:
        
        n = len(A)
        next_higher, next_lower = [0] * n, [0] * n

        stack = []
        for a, i in sorted([a, i] for i, a in enumerate(A)):
            while stack and stack[-1] < i:
                next_higher[stack.pop()] = i
            stack.append(i)
            
        stack = []
        for a, i in sorted([-a, i] for i, a in enumerate(A)):
            while stack and stack[-1] < i:
                next_lower[stack.pop()] = i
            stack.append(i)
            
        higher, lower = [0] * n, [0] * n
        higher[-1] = lower[-1] = 1
        for i in range(n - 2, -1, -1):
            higher[i] = lower[next_higher[i]]
            lower[i] = higher[next_lower[i]]
            
        return sum(higher)


class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        index = 0
        n = len(A)
        next_high = [0] * n
        next_low = [0] *n
        stack = []
        B = [[i, a] for i,a in enumerate(A)]
        B.sort(key = lambda x:x[1])
        for i, a in B:
            while stack and (stack[-1] < i):
                next_high[stack.pop()] = i
            stack.append(i)
        B.sort(key = lambda x:-x[1])
        stack = []
        for i, a in B:
            while stack and (stack[-1] < i):
                next_low[stack.pop()] = i
            stack.append(i)
        
        higher = [0] * n
        lower = [0] * n
        higher[-1] = lower[-1] = 1
        for i in range(n - 2, -1, -1):
            higher[i] = lower[next_high[i]]
            lower[i] = higher[next_low[i]]
        # print(higher, lower)
        return sum(higher)

class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        N = len(A)
        # returns a list of the index you can jump to from any index in A
        # runs twice since where you jump to on an even jump is diff than an odd jump
        def make(sorted_index_locations: [int]):
            # 'None' means no jump is possible from this index in A
            jump_to_locations = [None] * N

            # The stack is used to track indexes that you
            stack = []

            # now walk the list in order
            # if index_location > stack[-1], it means index_location is past stack[-1]
            # since sorted_index_locations is sorted smallest to largest, all smaller numbers are behind it
            # so it's finding the next-lowest number that's further up the list -- this is where it will jump to.

            for index_location in sorted_index_locations:
                while stack and index_location > stack[-1]:
                    # all items on the stack are smaller and are behind it in A
                    # so they'll jump to the same place this index will jump to
                    jump_to_locations[stack.pop()] = index_location
                # if stack is empty or this index is higher than the last on on the stack,
                # push this onto the stack and go to the next index
                stack.append(index_location)

            # jump_to_locations contains the location you jump, or None if you can't jump from that index
            return jump_to_locations

        B = sorted(list(range(N)), key=lambda i: A[i])
        odd_jump_to_locations = make(B)
        B.sort(key=lambda i: -A[i])
        even_jump_to_locations = make(B)

        # odd and even have 'good indexes' where they end up True after this.
        # initialize assuming only that the very last location (A[N-1]) will always be True.
        odd = [False] * N
        even = [False] * N
        odd[N - 1] = even[N - 1] = True

        for i in range(N - 2, -1, -1):
            if odd_jump_to_locations[i] is not None:
                odd[i] = even[odd_jump_to_locations[i]]
            if even_jump_to_locations[i] is not None:
                even[i] = odd[even_jump_to_locations[i]]

        return sum(odd)




class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        n = len(A)
        next_higher, next_lower = [0] * n, [0] * n

        stack = []
        for a, i in sorted([a, i] for i, a in enumerate(A)):
            while stack and stack[-1] < i:
                next_higher[stack.pop()] = i
            stack.append(i)

        stack = []
        for a, i in sorted([-a, i] for i, a in enumerate(A)):
            while stack and stack[-1] < i:
                next_lower[stack.pop()] = i
            stack.append(i)

        higher, lower = [0] * n, [0] * n
        higher[-1] = lower[-1] = 1
        for i in range(n - 1)[::-1]:
            higher[i] = lower[next_higher[i]]
            lower[i] = higher[next_lower[i]]
        return sum(higher)
                
                    
            
                
              


class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        
        n = len(A)
        next_higher, next_lower = [0] * n, [0] * n
        
        stack = []
        for a, i in sorted([a, i] for i, a in enumerate(A)):
            while stack and stack[-1] < i:
                next_higher[stack.pop()] = i
            stack.append(i)
        
        stack = []
        for a, i in sorted([-a, i] for i, a in enumerate(A)):
            while stack and stack[-1] < i:
                next_lower[stack.pop()] = i
            stack.append(i)
        
        validOddStartingPoints, validEvenStartingPoints = [0] * n, [0] * n
        validOddStartingPoints[-1] = validEvenStartingPoints[-1] = 1
        
        for i in range(n-2, -1, -1):
            validOddStartingPoints[i] = validEvenStartingPoints[next_higher[i]]
            validEvenStartingPoints[i] = validOddStartingPoints[next_lower[i]]
        
        return sum(validOddStartingPoints)

class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        odd_jump = {}
        even_jump = {}
        index_ele = {index: ele for index, ele in enumerate(A)}
        # {0: 10. 2: 12, 1: 13}
        sorted_A = sorted(list(range(len(A))), key=lambda x: A[x])
        even_sorted_A = sorted(list(range(len(A))), key=lambda x: (A[x], -x))
        # cache = {}
        # sorted(index_ele.items(), key=lambda kv: (kv[1], kv[0]))
        # print(sorted_A)
        # [1: 3, 1:2, 2:0, 3:1, 4:4]
        # [4: 4, 3: 1, 2:0. 1:2, 1:3]
        # [4, 1, 0, 3]
        stack = []
        # [1, 1, 2,3,4]
        for i in range(len(A)):
            idx = sorted_A[i]
            # idx = ele_index[ele]
            while stack and stack[-1] < idx:
                old_index = stack.pop()
                odd_jump[old_index] = idx
            stack.append(idx)
        for idx in stack:
            odd_jump[idx] = -1        
        stack = []
        for i in range(len(A) - 1, -1, -1):
            idx = even_sorted_A[i]
            # idx = ele_index[ele]
            while stack and stack[-1] < idx:
                old_index = stack.pop()
                even_jump[old_index] = idx
            stack.append(idx)
        for idx in stack:
            even_jump[idx] = -1
        self.ans = 0
        # print(odd_jump, even_jump)
        @lru_cache(None)
        def helper(index, odd):
            if index == len(A) - 1:
                # self.ans += 1
                return 1
            ans = 0
            if index == -1:
                return 0
            # if (index, odd) in self.cache: return self.cache[(index, odd)]
            if odd:
                # print(index)
                ans += helper(odd_jump[index], not odd)
            else:
                ans += helper(even_jump[index], not odd)
                # [10, 12, 13, 14, 15]
                # [0,   2,  1,  3,  4]
                # 1
                # 2   3   3  4 -1
                # [15, 14, 13, 12, 10]
                # [15, 14, 12, 10]
                #  -1        13: 2
            return ans
        ans = 0
        for i in range(len(A)):
            ans += helper(i, True)
        return ans


def get_nsge_ngse(a):
    ngse_stack = []
    nsge_stack = []
    ngse = [-1]*len(a)
    nsge = [-1]*len(a)
    for i,item in sorted(enumerate(a), key = lambda x: (x[1], x[0])):
        while nsge_stack and i > nsge_stack[-1]:
            nsge[nsge_stack.pop()] = i
        nsge_stack.append(i)
    for i,item in sorted(enumerate(a), key = lambda x: (-1*x[1], x[0])):
        while ngse_stack and i > ngse_stack[-1]:
            ngse[ngse_stack.pop()] = i
        ngse_stack.append(i)
    return(nsge, ngse)

def get_ways(a):
    odd, even = get_nsge_ngse(a)
    print(odd,even)
    dp =[set() for x in a]
    dp[-1].add('even')
    dp[-1].add('odd')
    count = 1
    for i in range(len(a)-2,-1,-1):
        if odd[i] !=-1 and 'even' in dp[odd[i]]:
            dp[i].add('odd')
        if even[i] !=-1 and 'odd' in dp[even[i]]:
            dp[i].add('even')
        if 'odd' in dp[i]:
            count +=1
    return count
            
            


class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        return get_ways(A)

class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        
        n = len(A)
        
        s1 = []
        s2 = []
        
        stack = []
        e = enumerate(A)
        order = sorted(e, key = lambda x: (x[1], x[0]))
        
        for i in reversed(list(range(n))):
            while stack and stack[-1] < order[i][0]:
                stack.pop()
            order[i] = (order[i][0],stack[-1]) if stack else (order[i][0],-1)
            stack.append(order[i][0])
        
        arr_odd = [-1] * n
        for i in range(n):
            arr_odd[order[i][0]] = order[i][1]
        
        stack = []
        e = enumerate(A)
        order = sorted(e, key = lambda x: x[1], reverse = True)
        for i in reversed(list(range(n))):
            while stack and stack[-1] < order[i][0]:
                stack.pop()
            order[i] = (order[i][0],stack[-1]) if stack else (order[i][0],-1)
            stack.append(order[i][0])
        
        arr_even = [-1] * n
        for i in range(n):
            arr_even[order[i][0]] = order[i][1]
        
        DP = [[False] * 2 for _ in range(n)]
        DP[n-1][0] = True
        DP[n-1][1] = True
        
        for i in reversed(list(range(n-1))):
            if arr_odd[i] == n-1:
                DP[i][0] = True
            elif arr_odd[i] != -1:
                DP[i][0] = DP[arr_odd[i]][1]
            
            if arr_even[i] == n-1:
                DP[i][1] = True
            elif arr_even[i] != -1:
                DP[i][1] = DP[arr_even[i]][0]
        
        count = 0
        for i in range(n):
            if DP[i][0] == True:
                count += 1
        
        return count


class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        if not A:
            return 0
        
        n = len(A)
        
        # get next pos for odd/even jumps
        next_pos = [[-1] * 2 for _ in range(n)]
        
        stack = []
        
        idxes = sorted([i for i in range(n)], key=lambda i: (A[i], i))
        
        for idx in idxes:
            while stack and stack[-1] < idx:
                next_pos[stack[-1]][1] = idx
                stack.pop()
            
            stack.append(idx)
        
        stack = []
        
        idxes = sorted([i for i in range(n)], key=lambda i: (-A[i], i))
        
        for idx in idxes:
            while stack and stack[-1] < idx:
                next_pos[stack[-1]][0] = idx
                stack.pop()
            
            stack.append(idx)
        
        dp = [[False] * 2 for _ in range(n)]
        
        ret = 0
        
        for i in range(n - 1, -1, -1):
            if i == n - 1:
                dp[i][0] = True
                dp[i][1] = True
                
            else:
            
                odd_next = next_pos[i][1]
                if odd_next == -1:
                    dp[i][1] = False
                else:
                    dp[i][1] = dp[odd_next][0]
                
                even_next = next_pos[i][0]
                if even_next == -1:
                    dp[i][0] = False
                else:
                    dp[i][0] = dp[even_next][1]
                    
            
            if dp[i][1] == True:
                ret += 1
        
        return ret
            
            
            
            
            
            
        
        
        
        
        
        
        
        # dp for odd/even jumps whether can get the end
        


class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        n = len(A)
        more = {}
        less = {}
        stack = []
        
        B = sorted(range(n), key=lambda i: A[i])
        for i in B:
            while stack and stack[-1] < i:
                more[stack.pop()] = i
                
            stack.append(i)
            
        B = sorted(range(n), key=lambda i: -A[i])
        for i in B:
            while stack and stack[-1] < i:
                less[stack.pop()] = i
                
            stack.append(i)
            
        count = 0
        for i in range(n):
            jumps = 1
            j = i
            while j < n - 1:
                if jumps % 2:
                    j = more[j] if j in more else None
                else:
                    j = less[j] if j in less else None
                    
                if j is None:
                    break
                
                jumps += 1
                    
            if j is not None:
                count += 1
                
        return count

class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        l = len(A)
        idxs = sorted(range(l), key=lambda i: A[i])
        odds = [-1] * l
        stack = []
        for i in idxs:
            while stack and stack[-1] < i:
                odds[stack.pop()] = i
            stack.append(i)
        idxs = sorted(range(l), key=lambda i: -A[i])
        evens = [-1] * l
        stack = []
        for i in idxs:
            while stack and stack[-1] < i:
                evens[stack.pop()] = i
            stack.append(i)
        reachable = [[-1, -1] for _ in range(l)]
        reachable[-1] = [1, 1]
        def helper(i, j):
            if reachable[i][j] >= 0:
                return reachable[i][j]
            if j == 0:
                reachable[i][j] = 0 if odds[i] == -1 else helper(odds[i], 1)
            else:
                reachable[i][j] = 0 if evens[i] == -1 else helper(evens[i], 0)
            return reachable[i][j]
        return sum(helper(i, 0) for i in range(l))

class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        N = len(A)
        
        nextSmallestLarger = [-1] * N
        indexes = sorted(range(N), key=lambda i: A[i])
        stk = []
        for i in indexes:
            while stk and i > stk[-1]:
                nextSmallestLarger[stk.pop()] = i
            stk.append(i)
        
        nextLargestSmaller = [-1] * N
        indexes = sorted(range(N), key=lambda i: -A[i])
        stk = []
        for i in indexes:
            while stk and i > stk[-1]:
                nextLargestSmaller[stk.pop()] = i
            stk.append(i)
        
        @lru_cache(None)
        def jump(i, odd):
            if i >= N - 1:
                return True
            
            if odd:
                return False if nextSmallestLarger[i] == -1 else jump(nextSmallestLarger[i], False)
            else:
                return False if nextLargestSmaller[i] == -1 else jump(nextLargestSmaller[i], True)
            
        return sum(jump(i, True) for i in range(N))

class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        N = len(A)
        # returns a list of the index you can jump to from any index in A
        # runs twice since where you jump to on an even jump is diff than an odd jump
        def make(sorted_index_locations: [int]):
            # 'None' means no jump is possible from this index in A
            jump_to_locations = [None] * N

            # The stack is used to track indexes that you
            stack = []

            # now walk the list in order
            # if index_location > stack[-1], it means index_location is past stack[-1]
            # since sorted_index_locations is sorted smallest to largest, all smaller numbers are behind it
            # so it's finding the next-lowest number that's further up the list -- this is where it will jump to.

            for index_location in sorted_index_locations:
                while stack and index_location > stack[-1]:
                    # all items on the stack are smaller and are behind it in A
                    # so they'll jump to the same place this index will jump to
                    jump_to_locations[stack.pop()] = index_location
                # if stack is empty or this index is higher than the last on on the stack,
                # push this onto the stack and go to the next index
                stack.append(index_location)

            # jump_to_locations contains the location you jump, or None if you can't jump from that index
            return jump_to_locations

        B = sorted(list(range(N)), key=lambda i: A[i])
        odd_jump_to_locations = make(B)
        B.sort(key=lambda i: -A[i])
        even_jump_to_locations = make(B)

        # odd and even have 'good indexes' where they end up True after this.
        # initialize assuming only that the very last location (A[N-1]) will always be True.
        odd = [False] * N
        even = [False] * N
        odd[N - 1] = even[N - 1] = True

        for i in range(N - 2, -1, -1):
            if odd_jump_to_locations[i] is not None:
                odd[i] = even[odd_jump_to_locations[i]]
            if even_jump_to_locations[i] is not None:
                even[i] = odd[even_jump_to_locations[i]]

        return sum(odd)



from functools import lru_cache

class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        
        next_larger_idx = [None] * len(A)
        next_smaller_idx = [None] * len(A)
        
        sorted_idx_asc = sorted(list(range(len(A))), key=lambda i: A[i])
        sorted_idx_desc = sorted(list(range(len(A))), key=lambda i: A[i], reverse=True)
        
        stack = []
        for idx in sorted_idx_asc:
            while stack and stack[-1] < idx: # we found next_larger_value in closest idx.
                prev_idx = stack.pop()
                next_larger_idx[prev_idx] = idx
            stack.append(idx)
        
        stack = []
        for idx in sorted_idx_desc:
            while stack and stack[-1] < idx: # we found next_smaller_value in closest idx.
                prev_idx = stack.pop()
                next_smaller_idx[prev_idx] = idx
            stack.append(idx)
                
        def get_next(idx, is_odd):
            if is_odd:
                return next_larger_idx[idx]
            else:
                return next_smaller_idx[idx]
                
        
        
        # Define helper
        @lru_cache(maxsize=len(A) * 3)
        def is_goalable_from(idx, is_odd):
            # Search next steps
            if idx == len(A) - 1:
                return True
            if is_odd:
                smallest_idx = get_next(idx, is_odd)
                if smallest_idx is None:
                    return False
                return is_goalable_from(smallest_idx, not is_odd)
            else: # even
                largest_idx = get_next(idx, is_odd)
                if largest_idx is None:
                    return False
                return is_goalable_from(largest_idx, not is_odd)
                
        # Main
        counts = 0
        for start_idx in range(len(A)):
            if is_goalable_from(start_idx, True):
                counts += 1
        return counts


class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        odd_jumps = {}
        stack = []
        for num, i in sorted([[num, i] for i, num in enumerate(A)], reverse = True):
            while stack and stack[-1][1] < i:
                stack.pop()
            if not stack:
                odd_jumps[i] = None
            else:
                odd_jumps[i] = stack[-1][1]
            stack.append([num, i])
            
        even_jumps = {}
        stack = []
        for num, i in sorted([[num, -i] for i, num in enumerate(A)]):
            i = -i
            while stack and stack[-1][1] < i:
                stack.pop()
            if not stack:
                even_jumps[i] = None
            else:
                even_jumps[i] = stack[-1][1]
            stack.append([num, i])
          
        n = len(A)
        @lru_cache(None)
        def dfs(i, is_odd):
            if i == n - 1:
                return True
            if is_odd and odd_jumps[i]:
                return dfs(odd_jumps[i], False) 
            elif not is_odd and even_jumps[i]:
                return dfs(even_jumps[i], True) 
            else:
                return False
        
        res = 0
        for i in range(n):
            res += 1 if dfs(i, True) else 0
        return res
                


class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        N = len(A)

        def make(B):
            ans = [None] * N
            stack = []  # invariant: stack is decreasing
            for i in B:
                while stack and i > stack[-1]:
                    ans[stack.pop()] = i
                stack.append(i)
            return ans

        B = sorted(range(N), key = lambda i: A[i])
        oddnext = make(B)
        B.sort(key = lambda i: -A[i])
        evennext = make(B)

        odd = [False] * N
        even = [False] * N
        odd[N-1] = even[N-1] = True

        for i in range(N-2, -1, -1):
            if oddnext[i] is not None:
                odd[i] = even[oddnext[i]]
            if evennext[i] is not None:
                even[i] = odd[evennext[i]]

        return sum(odd)

class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        def make_mono_stack(sorted_idxes):
            result = [None]*len(sorted_idxes)
            stack = []
            for idx in sorted_idxes:
                while stack and idx > stack[-1]:
                    result[stack.pop()] = idx
                stack.append(idx)
            return result
        
        n = len(A)
        sorted_idxes = sorted(list(range(n)), key=lambda i: A[i])
        odd_next = make_mono_stack(sorted_idxes)
        # sorted_idxes = sorted(range(n), key=lambda x: A[x], reverse=True)
        sorted_idxes.sort(key=lambda i: A[i], reverse=True)
        even_next = make_mono_stack(sorted_idxes)
        
        odd_can_reach_from_idx = [False]*n
        even_can_reach_from_idx = [False]*n
        # we can reach to last idx from last idx itself
        odd_can_reach_from_idx[-1]= even_can_reach_from_idx[-1] = True
        
        # iterate through A backwards, starting at next to last element
        for i in range(len(A) - 2, -1, -1):
            if odd_next[i] is not None:
                odd_can_reach_from_idx[i] = even_can_reach_from_idx[odd_next[i]]
            if even_next[i] is not None:
                even_can_reach_from_idx[i] = odd_can_reach_from_idx[even_next[i]]
        return sum(odd_can_reach_from_idx)
        


from collections import defaultdict

class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        cand = defaultdict(lambda: [set(), set()])
        stack, stack_dec = [], []
        for x, i in sorted([(x, i) for i, x in enumerate(A)]):
            while len(stack) > 0 and stack[-1][1] < i:
                cand[i][0].add(stack.pop()[1])
            stack.append((x, i))
        for x, i in sorted([(x, i) for i, x in enumerate(A)], key=lambda y: (-y[0], y[1])):
            while len(stack_dec) > 0 and stack_dec[-1][1] < i:
                cand[i][1].add(stack_dec.pop()[1])
            stack_dec.append((x, i))
        
        n = len(A)
        ans = {n - 1}
        for_odd, for_even = {n - 1}, {n - 1}
        time = 0
        
        while len(for_odd) > 0 or len(for_even) > 0:
            time += 1
            new_odd, new_even = set(), set()
            for x in for_odd:
                for y in cand[x][1]:
                    new_even.add(y)
            for x in for_even:
                for y in cand[x][0]:
                    new_odd.add(y)
            for x in new_odd:
                ans.add(x)
            for_odd, for_even = new_odd, new_even
        
        return len(ans)


class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        next_high = [0 for _ in range(len(A))]
        next_low = [0 for _ in range(len(A))]
        
        stack = []
        for val, i in sorted([(val, i) for i, val in enumerate(A)]):
            while stack and stack[-1] < i:
                next_high[stack.pop()] = i
            stack.append(i)
            
        stack = []
        for val, i in sorted([(-val, i) for i, val in enumerate(A)]):
            while stack and stack[-1] < i:
                next_low[stack.pop()] = i
            stack.append(i)
        
        dp = [[False for _ in range(len(A))] for _ in range(2)]
        dp[0][-1] = dp[1][-1] = True
        for i in range(len(A) - 2, -1, -1):
            dp[0][i] = dp[1][next_high[i]]
            dp[1][i] = dp[0][next_low[i]]

        return dp[0].count(1)


class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        N = len(A)

        def make(B):
            ans = [None] * N
            stack = []  # invariant: stack is decreasing
            for i in B:
                while stack and i > stack[-1]:
                    ans[stack.pop()] = i
                stack.append(i)
            return ans

        B = sorted(list(range(N)), key = lambda i: A[i])
        oddnext = make(B)
        B.sort(key = lambda i: -A[i])
        evennext = make(B)

        odd = [False] * N
        even = [False] * N
        odd[N-1] = even[N-1] = True

        for i in range(N-2, -1, -1):
            if oddnext[i] is not None:
                odd[i] = even[oddnext[i]]
            if evennext[i] is not None:
                even[i] = odd[evennext[i]]

        return sum(odd)


class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        #for all the odd jump, can only jump to number greater or equal
        #for all the even jump, can only jump to number less or equal
        
        n = len(A)
        odd_jump = [-1] * n 
        even_jump = [-1] * n
        
        final_odd = [False] * n 
        final_even = [False] * n 
        final_odd[-1] = True 
        final_even[-1] = True
        
        stack = []
        for n, i in sorted((n,i) for i,n in enumerate(A)):
            while stack and stack[-1] < i:
                odd_jump[stack.pop()] = i 
            stack.append(i)
        
        
        stack = []
        for n, i in sorted((-n,i) for i, n in enumerate(A)):
            while stack and stack[-1] < i:
                even_jump[stack.pop()] = i 
            stack.append(i)
        
     
        
        for i in range(len(A)-2,-1,-1):
            print(i)
            if odd_jump[i] != -1:
                final_odd[i] = final_even[odd_jump[i]]
            if even_jump[i] != -1:
                final_even[i] = final_odd[even_jump[i]]
        return sum(final_odd)
        


class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        n = len(A)
        
        next_higher = [0 for x in range(n)] 
        next_lower = [0 for x in range(n)]
        stack = []
        
        for a, i in sorted([a, i] for i, a in enumerate(A)):
            while stack and stack[-1] < i:
                next_higher[stack.pop()] = i
            stack.append(i)
        for a, i in sorted([-a, i] for i, a in enumerate(A)):
            while stack and stack[-1] < i:
                next_lower[stack.pop()] = i
            stack.append(i)
            

        higher = [0 for x in range(n)] 
        lower = [0 for x in range(n)]
        higher[-1] =  1
        lower[-1] = 1
        for i in range(n - 1)[::-1]:
            higher[i] = lower[next_higher[i]]
            lower[i] = higher[next_lower[i]]
        return sum(higher)

class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        n = len(A)
        next_higher, next_lower = [0]*n, [0]*n
        
        stack = []
        for a, i in sorted([a,i] for i,a in enumerate(A)):
            while stack and stack[-1] < i:
                next_higher[stack.pop()] = i
            stack.append(i)
        
        stack = []
        for a, i in sorted([-a, i] for i, a in enumerate(A)):
            while stack and stack[-1] < i:
                next_lower[stack.pop()] = i
            stack.append(i)
        
        higher, lower = [0]*n, [0]*n
        higher[-1] = lower[-1] = 1
        for i in range(n-1)[::-1]:
            higher[i] = lower[next_higher[i]]
            lower[i] = higher[next_lower[i]]
        return sum(higher)

class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        N = len(A)
        idxes = range(N)
        
        def make(B):
            ans = [None] * N
            stack = []
            for i in B:
                while stack and i > stack[-1]:
                    pop = stack.pop()
                    ans[pop] = i
                stack.append(i)
            return ans
        
        sorted_idxes = sorted(idxes, key=lambda i: A[i])
        oddnext = make(sorted_idxes)
        sorted_idxes_rev = sorted(idxes, key=lambda i: -A[i])
        evennext = make(sorted_idxes_rev)
        
        odd = [False] * N
        even = [False] * N
        
        odd[N-1] = True
        even[N-1] = True
        
        for i in range(N-2, -1, -1):
            if oddnext[i] is not None:
                odd[i] = even[oddnext[i]]
            if evennext[i] is not None:
                even[i] = odd[evennext[i]]
        #print(odd, even)
            
        #print(A, sorted_idxes, sorted_idxes_rev)
        return sum(1 for x in odd if x)

class Solution:
    def oddEvenJumps(self, A):
        n = len(A)
        next_higher, next_lower = [0] * n, [0] * n

        stack = []
        for a, i in sorted([a, i] for i, a in enumerate(A)):
            while stack and stack[-1] < i:
                next_higher[stack.pop()] = i
            stack.append(i)

        stack = []
        for a, i in sorted([-a, i] for i, a in enumerate(A)):
            while stack and stack[-1] < i:
                next_lower[stack.pop()] = i
            stack.append(i)

        higher, lower = [0] * n, [0] * n
        higher[-1] = lower[-1] = 1
        for i in range(n - 1)[::-1]:
            higher[i] = lower[next_higher[i]]
            lower[i] = higher[next_lower[i]]
        return sum(higher)

class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        n = len(A)
        
        next_higher = [0 for x in range(n)] 
        next_lower = [0 for x in range(n)]
        stack = []
        
        for a, i in sorted([a, i] for i, a in enumerate(A)):
            while stack and stack[-1] < i:
                next_higher[stack.pop()] = i
            stack.append(i)
        print(next_higher)
        #print(sorted([a, i] for i, a in enumerate(A)))
        for a, i in sorted([-a, i] for i, a in enumerate(A)):
            while stack and stack[-1] < i:
                next_lower[stack.pop()] = i
            stack.append(i)
            

        higher = [0 for x in range(n)] 
        lower = [0 for x in range(n)]
        higher[-1] =  1
        lower[-1] = 1
        for i in range(n - 1)[::-1]:
            higher[i] = lower[next_higher[i]]
            lower[i] = higher[next_lower[i]]
        return sum(higher)

import heapq
class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        mono_inc = sorted([(i, val) for i, val in enumerate(A)], key=lambda x:x[1])
        mono_dec = sorted(mono_inc, reverse=True, key=lambda x:x[1])
        
        odd_jumps = [None] * len(mono_inc)
        for i, el in enumerate(mono_inc):
            j = i + 1
            while j < len(mono_inc):
                next_el = mono_inc[j]
                if next_el[0] > el[0]:
                    odd_jumps[el[0]] = next_el[0]
                    break
                j += 1
        
        even_jumps = [None] * len(mono_dec)
        for i, el in enumerate(mono_dec):
            j = i + 1
            while j < len(mono_dec):
                next_el = mono_dec[j]
                if next_el[0] > el[0]:
                    even_jumps[el[0]] = next_el[0]
                    break
                j += 1
        
        odd = {}
        even = {}
        i = len(A) - 1
        while i >= 0:
            if i == (len(A) - 1):
                odd[i] = True
                even[i] = True
                i -= 1
                continue
            odd_dest = odd_jumps[i]
            odd[i] = even[odd_dest] if odd_dest is not None else False
            even_dest = even_jumps[i]
            even[i] = odd[even_dest] if even_dest is not None else False
            i -= 1
        return sum(odd.values())

class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        N = len(A)
        
        # preparation: sorted A
        aS = [(val, i) for i, val in enumerate(A)]
        aS.sort(key=lambda x: x[0])
        a_map = {}
        for id, (val, i) in enumerate(aS):
            a_map[i] = id
        dS = [(val, i) for i, val in enumerate(A)]
        dS.sort(key=lambda x: x[0], reverse=True)
        d_map = {}
        for id, (val, i) in enumerate(dS):
            d_map[i] = id
                
        # dp[i] tracks the validness for tarting index i, dp[i] = [x, y] where x, y = 1/0 indicating an (x) even jump or an (y) odd being valid or not
        dp = [[0,0]] * N
        dp[N - 1] = [1, 1]
        
        for i in range(N - 2, -1, -1):
            dp[i] = [0, 0]
            # even jump, find the biggest smaller one next
            id = d_map[i]
            while id + 1 < N: 
                val, j = dS[id + 1]
                if j > i: 
                    dp[i][0] = dp[j][1]
                    break
                id = id + 1
            # odd jump, find the smallest bigger one next
            id = a_map[i]
            while id + 1 < N: 
                val, j = aS[id + 1]
                if j > i: 
                    dp[i][1] = dp[j][0]
                    break
                id = id + 1
        
        # find the dp[i] with odd (1st) is 1
        cnt = 0
        for i in range(N):
            cnt += dp[i][1]
        
        return cnt
            
                    
            
        


class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        # Monotonic Stack
        # Time  complexity: O(NlogN)
        # Space complexity: O(N)
        # N = len(A)

        # def make(B):
        #     ans = [None] * N
        #     stack = []  # invariant: stack is decreasing
        #     for i in B:
        #         while stack and i > stack[-1]:
        #             ans[stack.pop()] = i
        #         stack.append(i)
        #     return ans

        # B = sorted(range(N), key=lambda i: A[i])
        # oddnext = make(B)
        # B.sort(key=lambda i: -A[i])
        # evennext = make(B)

        # odd = [False] * N
        # even = [False] * N
        # odd[N - 1] = even[N - 1] = True

        # for i in range(N - 2, -1, -1):
        #     if oddnext[i] is not None:
        #         odd[i] = even[oddnext[i]]
        #     if evennext[i] is not None:
        #         even[i] = odd[evennext[i]]

        # return sum(odd)


        n = len(A)
        next_higher, next_lower = [0] * n, [0] * n

        stack = []
        for a, i in sorted([a, i] for i, a in enumerate(A)):
            while stack and stack[-1] < i:
                next_higher[stack.pop()] = i
            stack.append(i)

        stack = []
        for a, i in sorted([-a, i] for i, a in enumerate(A)):
            while stack and stack[-1] < i:
                next_lower[stack.pop()] = i
            stack.append(i)

        higher, lower = [0] * n, [0] * n
        higher[-1] = lower[-1] = 1

        for i in range(n - 1)[::-1]:
            higher[i] = lower[next_higher[i]]
            lower[i] = higher[next_lower[i]]

        return sum(higher)


class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        # [ 0, 1, 2, 3, 4]
        # [10,13,12,14,15]
        
        # [ 0, 2, 1, 3, 4]
        # [10,12,13,14,15]
        # [-15,-14,-13,-12,-10]
        
        # [ 0, 2, 1, 3, 4]
        # [ 0, 2, 2, 3, 4]
        
        # [12,14,14,15,15] - odds_next
        # [10,12,12,14,15] - evens_next
        
        # [ N, N, N, Y, Y]
        # [ N, N, N, N, Y]
        
        increasing = [(v, i) for i, v in enumerate(A)]
        increasing.sort()
        increasing = [item[1] for item in increasing]
        decreasing = [(v, i) for i, v in enumerate(A)]
        decreasing.sort(key=lambda item: item[0] * -1)
        decreasing = [item[1] for item in decreasing]
            
        odds_next = make(increasing)
        evens_next = make(decreasing)
        
        odds = [False for i in range(len(A))]
        odds[len(A) - 1] = True
        evens = [False for i in range(len(A))]
        evens[len(A) - 1] = True
        results = [len(A) - 1]
        for i in reversed(list(range(len(A) - 1))):
            if odds_next[i] > i and evens[odds_next[i]]:
                odds[i] = True
                results.append(i)
            if evens_next[i] > i and odds[evens_next[i]]:
                evens[i] = True
        print(results)
        return len(results)
                
        
def make(arr):
    output = [i for i in range(len(arr))]
    stack = []
    for i in range(len(arr)):
        value = arr[i]
        while stack and value > stack[-1]:
            index = stack.pop()
            output[index] = value
        stack.append(value)
    return output
        


class Solution:
    # O(nlog(n)) Time | O(n) Space
    def oddEvenJumps(self, A: List[int]) -> int:
        nextHigher = [0] * len(A)
        nextLower = [0] * len(A)
        validOdd = [0] * len(A)
        validEven = [0] * len(A)
        validOdd[-1] = 1
        validEven[-1] = 1
        
        stack = []
        #sort array by value, put all smaller valunes' index in stack, if stack[-1] smaller then current index, A[stack[-a]] next higher value is at index i
        for a, i in sorted([a, i] for i, a in enumerate(A)):
            while stack and stack[-1] < i:
                nextHigher[stack.pop()] = i
            stack.append(i)
        
        stack = []
        for a, i in sorted([-a, i] for i, a in enumerate(A)):
            while stack and stack[-1] < i:
                nextLower[stack.pop()] = i
            stack.append(i)
        
        for index in reversed(range(len(A) - 1)):
            validOdd[index] = validEven[nextHigher[index]]
            validEven[index] = validOdd[nextLower[index]]
        return sum(validOdd)

class Solution:
    def findIndex(self, arr, val):
        if not arr:
            return 0
        
        start = 0
        end = len(arr)-1
        while start < end:
            mid = start + (end - start)//2
            if arr[mid][0] < val:
                start = mid + 1
            else:
                end = mid
        if arr[start][0] < val:
            start += 1
        return start
    def oddEvenJumps(self, A: List[int]) -> int:
        n = len(A)
        
        odd = [False]*n
        even = [False]*n
        
        odd[-1] = even[-1] = True
        arr = [[A[-1], n-1]]

        count = 1
        for index in range(n-2, -1, -1):
            val = A[index]
            insindex = self.findIndex(arr, val)
            
            evenindex = None
            if insindex < len(arr):
                odd[index] = even[arr[insindex][1]]
                if arr[insindex][0] == val:
                    evenindex = arr[insindex][1]
                elif insindex > 0:
                    evenindex = arr[insindex-1][1]
            
            else:
                evenindex = arr[insindex-1][1]
            
            if evenindex is not None:
                even[index] = odd[evenindex]
            
            if insindex < len(arr) and arr[insindex][0] == val:
                arr[insindex][1] = index
            else:
                arr.insert(insindex, [val, index])
            
            if odd[index]:
                count += 1
        return count


from collections import deque

class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        size = len(A)
        if size < 2:
            return size
        oddNext = [-1] * size
        evenNext= [-1] * size
        def getNext(arr: list, nextArr: list):
            stack = deque()
            for index in arr:
                while stack and stack[-1] <= index:
                    nextArr[stack[-1]] = index
                    stack.pop()
                stack.append(index)
        indexes = sorted(list(range(size)), key = lambda i: A[i])
        getNext(indexes, oddNext)
        indexes = sorted(list(range(size)), key = lambda i: -A[i])
        getNext(indexes, evenNext)
        odds = [False] * size
        evens = [False] * size
        odds[size - 1] = True
        evens[size - 1] = True
        for index in range(size - 2, -1, -1):
            if evenNext[index] >= 0 and odds[evenNext[index]]:
                evens[index] = True
            if oddNext[index] >= 0 and evens[oddNext[index]]:
                odds[index] = True
        return sum([1 for isGood in odds if isGood])

class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        
        n = len(A)
        
        
        even = {}
        odd = {}
        stack = []
        
        ascending_idx = sorted([i for i in range(n)], key = lambda i: A[i])
        for idx in ascending_idx:
            while stack and idx>stack[-1]:
                odd[stack.pop()]=idx
            stack.append(idx)
        
        stack = []
        descending_idx = sorted([i for i in range(n)], key = lambda i: -A[i])
        for idx in descending_idx:
            while stack and idx>stack[-1]:
                even[stack.pop()]=idx
            stack.append(idx)
        del stack
                      
        res = 0
        for key in list(odd.keys()):
            if odd[key]==n-1: res += 1
            else:
                nxt = odd[key]
                jumps ,other = 0, even
                while nxt in other:
                    jumps += 1
                    nxt = even[nxt] if jumps%2!=0 else odd[nxt]
                    if nxt == n-1: 
                        res+=1
                        break
                    other = even if jumps%2==0 else odd
        
        return res+1


class Solution:
    def oddEvenJumps(self, B: List[int]) -> int:
        A = [[v, i] for i, v in enumerate(B)]
        A.sort()
        nextHigher = [len(A)] * (len(A) + 1)
        nextSmaller = [len(A)] * (len(A) + 1)
        stack = collections.deque()
        for v, i in A:
            while stack and stack[-1] < i:
                nextHigher[stack.pop()] = i
            stack.append(i)
            

        stack = collections.deque()
        A = [[-v, i] for i, v in enumerate(B)]
        A.sort()
        for v, i in A:
            while stack and stack[-1] < i:
                nextSmaller[stack.pop()] = i
            stack.append(i)
        
        dp = [[False, False] for _ in range(len(A) + 1)]
        dp[-2] = [True, True] # even, odd jump
        res = 1
        for i in range(len(A) - 2, -1, -1):
            nH, nL = nextHigher[i], nextSmaller[i]
            dp[i][0] = dp[nL][1]
            dp[i][1] = dp[nH][0]
            res += dp[i][1]
        return res

class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        '''
        Algorithm
        ---------
        We need to jump alternatively higher and lower until we reach the end of the array.
        '''
        
        stack = []
        
        n = len(A)
        next_higher, next_lower = [0] * n, [0] * n
        
        for _, i in sorted([val, index] for index, val in enumerate(A)):
            # Check if the index at the top of the stack
            # is less than the current index i. If it is
            # then the current index i is the next greater element for the index at the top of the stack
            while stack and stack[-1] < i:
                next_higher[stack.pop()] = i
            stack.append(i)
        
        stack = []
        for _, i in sorted([-val, index] for index, val in enumerate(A)):
            while stack and stack[-1] < i:
                next_lower[stack.pop()] = i
            stack.append(i)
        
        higher, lower = [0] * n, [0] * n
        
        # increment the last index in both the lower and higher
        # since we know that the end of the array can be reached from the
        # last index
        higher[-1] += 1
        lower[-1] += 1
        
        for i in reversed(list(range(n - 1))):
            higher[i] = lower[next_higher[i]]
            lower[i] = higher[next_lower[i]]
        return sum(higher)
        


class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        n = len(A)
        next_higher, next_lower = [0] * n, [0] * n

        stack = []
        #print(sorted([-a, i] for i, a in enumerate(A)))
        for a, i in sorted([a, i] for i, a in enumerate(A)):
            while stack and stack[-1] < i:
                next_higher[stack.pop()] = i
            stack.append(i)
        #print(next_higher)
        
        stack = []
        for a, i in sorted([-a, i] for i, a in enumerate(A)):
            while stack and stack[-1] < i:
                next_lower[stack.pop()] = i
            stack.append(i)
            
        #print(next_lower)
        higher, lower = [0] * n, [0] * n
        higher[-1] = lower[-1] = 1
        for i in range(n - 1)[::-1]:
            higher[i] = lower[next_higher[i]]
            lower[i] = higher[next_lower[i]]
        return sum(higher)

class Solution:
    def oddEvenJumps(self, A):
        n = len(A)
        next_higher, next_lower = [0] * n, [0] * n

        stack = []
        for a, i in sorted([[a, i] for i, a in enumerate(A)]):
            while stack and stack[-1] < i:
                next_higher[stack.pop()] = i
            stack.append(i)

        stack = []
        for a, i in sorted([[-a, i] for i, a in enumerate(A)]):
            while stack and stack[-1] < i:
                next_lower[stack.pop()] = i
            stack.append(i)

        def jump(index, jump_num):
            if index == n-1:
                return 1
            next_index = 0
            if jump_num % 2 == 1:
                next_index = next_higher[index]
            else:
                next_index = next_lower[index]
            return jump(next_index, jump_num+1) if next_index else 0
        
        result = 0
        for start in range(n):
            result += jump(start, 1)
        return result

class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        curr_list = []
        smaller = []
        larger = []
        
        def find_insertion(ele):
            left = 0
            right = len(curr_list)
            
            while left < right:
                middle = (left + right)//2
                
                if curr_list[middle] < ele:
                    left = middle + 1
                else:
                    right = middle
                    
            return left
        
        for i in range(1, len(A) + 1):
            index = find_insertion([A[-i], len(A)-i])
            
            if index < len(curr_list) and curr_list[index][0] == A[-i]:
                smaller.append(curr_list[index][1])
                larger.append(curr_list[index][1])
                curr_list[index][1] = len(A) - i
                
            
            else:
                if index > 0:
                    smaller.append(curr_list[index - 1][1])
                else:
                    smaller.append(None)
                if index < len(curr_list):
                    larger.append(curr_list[index][1])                
                else:
                    larger.append(None)

                curr_list.insert(index, [A[-i], len(A)-i])
            
        
        smaller.reverse()
        larger.reverse()
        
        can_reach_odd = [False]*len(A)
        can_reach_even = [False]*len(A)
        
        can_reach_odd[-1] = True
        can_reach_even[-1] = True
        
        #print(smaller)
        #print(larger)
        #print(curr_list)
        
        
        for i in range(2, len(A) + 1):
            if larger[-i] != None:
                can_reach_odd[-i] = can_reach_even[larger[-i]]
            if smaller[-i] != None:
                can_reach_even[-i] = can_reach_odd[smaller[-i]]
            
        solution = 0
        for i in can_reach_odd:
            if i:
                solution += 1
        
        return solution
            
        


class Solution:
    def oddEvenJumps(self, A: List[int]) -> int:
        n = len(A)
        next_higher, next_lower = [0] * n, [0] * n

        stack = []
        for a, i in sorted([a, i] for i, a in enumerate(A)):
            while stack and stack[-1] < i:
                next_higher[stack.pop()] = i
            stack.append(i)

        stack = []
        for a, i in sorted([-a, i] for i, a in enumerate(A)):
            while stack and stack[-1] < i:
                next_lower[stack.pop()] = i
            stack.append(i)

        higher, lower = [0] * n, [0] * n
        higher[-1] = lower[-1] = 1
        for i in range(n - 1)[::-1]:
            higher[i] = lower[next_higher[i]]
            lower[i] = higher[next_lower[i]]
        return sum(higher)