Discrete Centrifugal Jumps SOLUTION
There are n lovely high rises in New York, the stature of the I-th one is hey. Today a few miscreants have set ablaze first n−1 of them, and now the main security building is n-th high rise.
How about we call a bounce from I-th high rise to j-th (i<j) discrete, if all high rises between are carefully lower or higher than them two. Officially, hop is discrete, if i<j and one of the accompanying conditions fulfilled:
Right now, Vasya is remaining on the primary high rise and needs to live somewhat more, so he will likely arrive at n-th high rise with negligible check of discrete hops. Help him with calcualting this number.
The main line contains a solitary whole number n (2≤n≤3⋅105) — aggregate sum of high rises.
The subsequent line contains n numbers h1,h2,… ,hn (1≤hi≤109) — statures of high rises.
Print single number k — negligible measure of discrete hops. We can show that an answer consistently exists.
1 3 1 4 5
4 2 4
100 1 100 1 100
In the first testcase, Vasya can hop in the accompanying way: 1→2→4→5.
In the second and third testcases, we can arrive at last high rise in one hop.
Grouping of hops in the fourth testcase: 1→3→5.