Problem Description

Farmer John has $N\ (N\le 3\times 10^5)$ cows with heights $1, 2, \ldots, N$. One day, the cows line up in some order to play frisbee. Let $h_1 \ldots h_N$ denote the cows' heights in this order (so $h$ is a permutation of $1 \ldots N$).

Two cows at positions $i$ and $j$ in the line can successfully throw a frisbee back and forth if and only if every cow between them has height less than $\min(h_i, h_j)$.

Compute the sum of distances over all pairs of positions $i<j$ such that the two cows can successfully throw a frisbee back and forth. The distance between positions $i$ and $j$ is $j-i+1$.

Input Format

The first line contains an integer $N$. The second line contains $h_1 \ldots h_N$, separated by spaces.

Output Format

Output the sum of distances between all pairs of positions $i<j$ where the cows can successfully throw a frisbee back and forth. Note that the integers in this problem may require a 64-bit integer type (for example, "long long" in C or C++).

7
4 3 1 2 5 6 7

24

Hint

【Sample Explanation】

In this example, the valid position pairs are:

(1, 2), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (4, 5), (5, 6), (6, 7)

【Constraints】

• Testcases 1-3 satisfy $N\le 5000$.

• Testcases 4-11 have no additional constraints.

Translated by ChatGPT 5