Farmer John's \(N\) cows (\(N \leq 3 \times 10^5)\) have heights \(1, 2, \ldots, N\). One day, the cows are
standing in a line in some order playing frisbee; let \(h_1 \ldots h_N\) denote
the heights of the cows in this order (so the \(h\)'s are a permutation of
\(1 \ldots N\)).

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

Please compute the sum of distances between all pairs of locations \(i at
which there resides a pair of cows that can successfully throw the frisbee back
and forth. The distance between locations \(i\) and \(j\) is \(j-i+1\).

Problem credits: Quanquan Liu

SCORING

• Test cases 1-3 satisfy \(N\le 5000\).
• Test cases 4-11 satisfy no additional constraints.

Problem credits: Quanquan Liu

The first line of input contains a single integer \(N\). The next line of input
contains \(h_1 \ldots h_N\), separated by spaces.

Output the sum of distances of all pairs of locations at which there are cows
that can throw the frisbee back and forth. Note that the large size of
integers involved in this problem may require the use of 64-bit integer data
types (e.g., a "long long" in C/C++).

riseoj 작성

출처 올림피아드 > USACO > 2021-2022 > January > Silver