You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小 Z 厌倦了求解最大值，因此，小 Y 给小 Z 出了一个次大值问题。

小 Y 会给小 Z 一个 $1\sim n$ 每个数各出现一次的排列，$a_1,a_2,\dots,a_n$，并且给定一个定义 $f(l,r)$ 表示区间 $[l,r]$，即 $a_l,a_{l+1},\dots,a_r$ 中的次大值。

小 Y 要求小 Z 求出 $\sum f(l,r)$，其中 $1\le l < r \le n$，即对排列中的所有区间 $[l,r]$ 的次大值进行求和。

现在，小 Z 将这个难题交给了你。

输入格式

第一行一个整数 $n$，表示整数个数。

第二行共 $n$ 个整数，$a_1,a_2,\dots,a_n$ 表示一个排列。

输出格式

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

样例 #1

样例输入 #1

3
2 3 1

样例输出 #1

5

样例 #2

样例输入 #2

8
8 2 7 3 4 5 6 1

样例输出 #2

136

提示

【样例 1 解释】

区间 $[1,2],[1,3]$ 的次大值是 $2$，区间 $[2,3]$ 的次大值是 $1$，对所有区间的次大值求和为 $2+2+1=5$。

【数据范围】

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

对于 $60\%$ 的数据，满足 $n\le 5000$；

对于 $100\%$ 的数据，满足 $n\le 10^5$。