该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

压轴：次大值问题

题目背景

就如置身夜晚间隙 我于行驶的电车中随车摇晃 独自看向窗外那向后流动的景色 坐于窗边 看向窗外 看向美景 午后的阳光 也被夕阳染作橙色 渐渐将蓝色天空压至地平线下 就好似珍惜那最后的光芒一般 我的目光随之而去 只因为 今天 就此道别 by @wbh

题目描述

mywwzh 厌倦了求解最大值，因此，rgw 给 mywwzh 出了一个次大值问题。

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

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

因为众所周知，mywwzh非常忙，所以现在，mywwzh 将这个难题交给了你。

输入格式

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

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

输出格式

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

样例 #1

样例输入 #1

3
2 3 1

样例输出 #1

5

提示

[数据范围]

对于 $100\%$ 的数据，满足 $5000 \le n\le 10^5$，$1 \leq a_i < n$。

[重要说明]

因为考察知识点的不同，本题禁止使用单调栈做法，会进行人工代码审核。