COI '06 #1 Patrik

View as PDF

Submit solution

Points: 10
Time limit: 0.3s
Python 1.0s
Memory limit: 32M
Python 64M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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 Specification

The first line of input contains an integer N (1 \le N \le 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.

Output Specification

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

Sample Input


Sample Output