Croatian Olympiad in Informatics 2007

Task 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.

Input

The 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 231 nanometres.

The heights are given in the order in which people are standing in line.

Output

Output the number of pairs of people that can see each other on a single line.

Sample Input

7
2
4
1
2
2
5
1

Sample Output

10

All Submissions
Best Solutions


Point Value: 10
Time Limit: 0.50s
Memory Limit: 64M
Added: Jul 11, 2013

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)


This is rather obvious given the constraint N ≤ 500 000...

"Everyone will be shorter than 2^31 nanometres."

IT'S A TRAP LOLZZZZ