Description

在绍兴市编程达人的聚会中，厌倦了求最大值的新昌小伙伴想出了一个求次大值的方案，想来考考大家。给定一个 1 到 n 的数字各出现一次的排列 a[1]、a[2]、…、a[n]，定义 f(l,r)表示 a[l]、a[l+1]、a[l+2]、…、a[r]中的次大值，你需要求出对于所有的 1<=i<j<=n，f(i,j)的和。

Input Format

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

Output Format

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

3
2 3 1

5

Hint

样例 1：区间[1,2]和[1,3]的次大值是 2，区间[2,3]的次大值是 1，求和后的结果为 5。 对于 30%的数据，n<=100；
对于 70%的数据，n<=5000；
对于 100%的数据，n<=100000。