Simple Permutation Problem

Interview

Time limit1sMemory limit1024 MB

Summary

Count position pairs i < j in a permutation where both values are larger than every element strictly between them.

Level: Medium5 of 10
Topics: Stack, Array
Solved: No attempts yet

Problem

A permutation $P$ of length $N$ is given. A permutation of length $N$ uses each integer from $1$ to $N$ exactly once, arranged in any order. Count the pairs $(i, j)$ that satisfy both conditions below.

$1 \le i < j \le N$
$\min(P_i, P_j) > \max(0, P_{i+1}, P_{i+2}, \cdots, P_{j-1})$

$P_i$ is the $i$ -th element of $P$ .

Input

The first line contains $N$ , the length of the permutation.

The second line contains $N$ integers $P_1, P_2, \cdots, P_N$ , separated by spaces.

Output

Print the answer to the problem.

Constraints

$1 \le N \le 200{,}000$

Examples3

Example 1
Input
```
5
4 2 3 1 5
```
Expected output
```
7
```
Example 2
Input
```
4
3 2 1 4
```
Expected output
```
5
```
Example 3
Input
```
2
2 1
```
Expected output
```
1
```