P8094 [USACO22JAN] Cow Frisbee S

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

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

Output the sum of distances between all pairs of positions $i

【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