1. You are given an integer array A. From some starting index, you can make a series of jumps. 2. 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. 3. You jump forward from index i 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 if and only if 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 if and only if 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.) 4. You have to return the count of "good starting index". 5. 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.) 6. Last index is always a good starting index. Example 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.
Input Format
First line contains N. Second line contains N integer values.
Output Format
An integer value.
Constraints
1 <= A.length <= 20000 0 <= A[i] < 100000
Notice
Try First, Check Solution later
1. You should first read the question and watch the question video.2. Think of a solution approach, then try and submit the question on editor tab.3. We strongly advise you to watch the solution video for prescribed approach.Example
Input
5 10 13 12 14 15
Output
2