Patrik
N people are waiting in line to enter a concert. People get bored waiting so they turn and look for someone familiar in the line. Two persons A and B standing in line can see each other if they're standing right next to each other or if no person between them is strictly taller than person A or person B. Write a program that determines the number of pairs of people that can see each other.
InputThe first line of input contains an integer N (1 ≤ N ≤ 500 000), the number of people standing in line. Each of the following N lines contains a single integer, the height of one person in nanometres. Everyone will be shorter than 2^{31} nanometres. The heights are given in the order in which people are standing in line.
OutputOutput the number of pairs of people that can see each other on a single line.
Input
Output
7
2
4
1
2
2
5
1 Output
10Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.