题目描述

在绍兴市编程达人的聚会中，厌倦了求最大值的新昌小伙伴想出了一个求次大值的方案，想来考考大家。

给定一个1到$n$的数字各出现一次的排列$a[1]、a[2]、…、a[n]$，定义$f(l,r)$表示$a[l]、a[l+1]、a[l+2]、…、a[r]$中的次大值，你需要求出对于所有的$1 \le i < j \le n$，$f(i,j)$的和。

输入格式

第一行一个整数$n$，第二行$n$个整数表示$a[i]$。

输出格式

一行一个整数，表示答案。

输入输出样例

3
2 3 1

5

8
8 2 7 3 4 5 6 1

136

说明/提示

【样例解释】

样例1：区间[1,2]和[1,3]的次大值是2，区间[2,3]的次大值是1，求和后的结果为5。

【数据范围约定】

对于30%的数据，$n \le 100$；

对于70%的数据，$n \le 5000$；

对于100%的数据，$n \le 100000$