LC975. Odd Even Jump

class Solution:
       def oddEvenJumps(self, A):
            """    tc O(NlgN)   sc O(N)
            
            """
            n = len(A)
            next_higher_idx, next_lower_idx = [0] * n, [0] * n
            # step1 cache start odd jump, next position
            st = []
            for a,i in sorted([a,i] for i, a in enumerate(A)):
                while st and st[-1]  < i : 
                    # st cache all the non-incresing value's idx until value off stack top  finds the first number bigger than it 
                    next_higher_idx[st.pop()] = i
                st.append(i)
            
            # step2 cache start even jump, next position 
            st = [] 
            # note here we don't use reverse sort, we just sort my value, otherwise the order with same value will be reversed too 
            for a,i in sorted([-a,i] for i, a in enumerate(A)):
                while st and st[-1] < i:
                    next_lower_idx[st.pop()] = i
                st.append(i)
            # initialize lower, higher status 
            lower, higher = [0] * n, [0] * n 
            lower[-1] = higher[-1] = 1
            # cnt all higher successful cases
            # start from last 2nd 
            for i in range(n-1)[::-1]:
                higher[i] = lower[next_higher_idx[i]]
                lower[i] = higher[next_lower_idx[i]]
            return sum(higher)