#M0053. 次大值问题
次大值问题
题目描述
小 Z 厌倦了求解最大值,因此,小 Y 给小 Z 出了一个次大值问题。
小 Y 会给小 Z 一个 每个数各出现一次的排列,,并且给定一个定义 表示区间 ,即 中的次大值。
小 Y 要求小 Z 求出 ,其中 ,即对排列中的所有区间 的次大值进行求和。
现在,小 Z 将这个难题交给了你。
输入格式
第一行一个整数 ,表示整数个数。
第二行共 个整数, 表示一个排列。
输出格式
一行一个整数,表示答案。
输入输出样例
3
2 3 1
5
8
8 2 7 3 4 5 6 1
136
提示
【样例 1 解释】
区间 的次大值是 ,区间 的次大值是 ,对所有区间的次大值求和为 。
【数据范围】
对于 的数据,满足 ;
对于 的数据,满足 ;
对于 的数据,满足 。