#USACOC2223B. Cow Frisbee

Cow Frisbee

Description

Farmer John's NN cows (N3×105)N \leq 3 \times 10^5) have heights 1,2,,N1, 2, \ldots, N. One day, the cows arestanding in a line in some order playing frisbee; let h1hNh_1 \ldots h_N denotethe heights of the cows in this order (so the hh's are a permutation of1N1 \ldots N).

Two cows at positions ii and jj in the line can successfully throw the frisbeeback and forth if and only if every cow between them has height lower thanmin(hi,hj)\min(h_i, h_j).

Please compute the sum of distances between all pairs of locations i<ji<j atwhich there resides a pair of cows that can successfully throw the frisbee backand forth. The distance between locations ii and jj is ji+1j-i+1.

Input Format

The first line of input contains a single integer NN. The next line of inputcontains h1hNh_1 \ldots h_N, separated by spaces.

Output Format

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

7
4 3 1 2 5 6 7
7
4 3 1 2 5 6 7

Scoring

  • Test cases 1-3 satisfy N5000N\le 5000.
  • Test cases 4-11 satisfy noadditional constraints.

Problem Credit

Problem credits: Quanquan Liu