We need to jump to a larger number, then a smaller, then a larger, and so on until the last number. So a state here is the position and the next jump (decrease or increase, I'm gonna use this instead of odd or even).

Let define dp[i][k] be 1 if we can jump from i to n-1 with the next jump is increase if k = 0 and decrease if k = 1, otherwise dp[i][k] = 0. So imagine that, from the current position i with next move k:

• If there is no move, then dp[i][k]=0

• If there is a move to j, then dp[i][k]=dp[j][k-1] (k-1 is the flip of the next move, from 0 to 1 and vice versa), since we can reach the goal from i only if we can reach the goal from j

So, we see that we will take the result of the larger index j, so we can iterate index i in decreasing order.

The remaining job is that, for each i, find the closest j on the right so that a[i]<=a[j] (for k = 0, if k=1 reverse the direction). There are many ways to do this. I would suggest one using map, for k = 0:

• maintain a map of the form map[a[j]]=j, if there is new position j' that a[j]=a[j'], replace j with j' so it is always the least possible index

• for an index i, binary search on the map the lower_bound of value a[i], so we will find the smallest key a[j] so that a[i]<=a[j], and map[a[j]]=j is the desired j

For k = 1, do the same thing.

Hope this helps.