2020 Mid-Atlantic USA Regional Contest

Start

2021-03-06 10:00 AKST

2020 Mid-Atlantic USA Regional Contest

End

2021-03-06 15:00 AKST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -223 days 15:56:54

Time elapsed

5:00:00

Time remaining

0:00:00

Problem D
Dominating Duos

A group of people are standing in a line. Each person has a distinct height. You would like to count the number of unordered pairs of people in the line such that they are taller than everyone in between them in the line.

More formally, let $d$ be a sequence of the heights of the people in order from left to right. We want to count the number of pairs of indices $i$ and $j$ with $i<j$ such that for all $k$ with $i < k < j$, $d_ i>d_ k$ and $d_ j>d_ k$. Note that if $j=i+1$ (i.e., there are no $k$’s between $i$ and $j$), it is trivially true.

Input

The first line of input contains an integer $n$ ($2 \le n \le 10^6$), which is the number of people.

Each of the next $n$ lines contains a single integer $d_ i$ ($1 \le d_ i \le n$). These are the heights of the people in the group, in the order in which they’re standing. The sequence is guaranteed to be a permutation of the integers $1$ through $n$.

Output

Output a single integer, which is the number of pairs of people who are taller than everyone between them.

Sample Input 1 Sample Output 1
3
2
1
3
3
Sample Input 2 Sample Output 2
6
1
3
2
6
4
5
7