#PU1183. USACO 2022 January Contest, Silver — Problem 2. Cow Frisbee
USACO 2022 January Contest, Silver — Problem 2. Cow Frisbee
USACO 2022 January Contest, Silver — Problem 2. Cow Frisbee
题目描述
Farmer John's cows ( have heights . One day, the cows are standing in a line in some order playing frisbee; let denote the heights of the cows in this order (so the 's are a permutation of ). Two cows at positions and in the line can successfully throw the frisbee back and forth if and only if every cow between them has height lower than . Please compute the sum of distances between all pairs of locations at which there resides a pair of cows that can successfully throw the frisbee back and forth. The distance between locations and is .
输入格式
The first line of input contains a single integer . The next line of input contains , separated by spaces.
输出格式
(见题面原文)
数据范围
Test cases 1-3 satisfy . Test cases 4-11 satisfy no additional constraints. Problem credits: Quanquan Liu
样例
样例 1
7
4 3 1 2 5 6 7
24
The pairs of successful locations in this example are as follows:
(1, 2), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (4, 5), (5, 6), (6, 7)