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 2³¹ 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