题目描述
农夫约翰的N头牛(N≤3×10⁵)身高分别为1、2、……、N。某天,这些牛排成一列玩飞盘,用h₁h₂……hₙ表示它们的当前身高顺序(h是1到N的一个排列)。若队列中位置i和j的两头牛能成功来回传递飞盘,当且仅当它们之间的所有牛的身高都严格小于hᵢ和hⱼ。
输入格式
输入的第一行包含一个整数N。输入的第二行包含用空格分隔的h₁到hN。
输出格式
输出所有能互相传递飞盘的牛所在位置对的距离之和。注意,本题中涉及的整数可能很大,需要使用64位整数数据类型(例如C/C++中的long long)。
输入输出样例
输入 输出 7 24 4 3 1 2 5 6 7
说明/提示
本例中成功的牛位置对如下:
(1, 2)、(1, 5)、(2, 3)、(2, 4)、(2, 5)、(3, 4)、(4, 5)、(5, 6)、(6, 7)