题目描述
在绍兴市编程达人的聚会中，厌倦了求最大值的新昌小伙伴想出了一个求次大值的方案，想来考考大家。
给定一个1到n的数字各出现一次的排列a[1]、a[2]、…、a[n]，定义f(l,r)表示a[l]、a[l+1]、a[l+2]、…、a[r]中的次大值，你需要求出对于所有的1<=i
输入
第一行一个整数n，第二行n个整数表示a[i]。
输出
一行一个整数，表示答案。
样例输入输出
输入#2
复制
8
8 2 7 3 4 5 6 1
提示
【样例解释】
样例1：区间[1,2]和[1,3]的次大值是2，区间[2,3]的次大值是1，求和后的结果为5。
【数据范围约定】
对于30%的数据，n<=100；
对于70%的数据，n<=5000；
对于100%的数据，n<=100000。