题目描述

在某个学校的趣味游戏活动中，$N$ 名同学站成一排，他们的年龄恰好是 $1$ 到 $N$。需要注意的是他们并不是按照年龄的大小排列的，而是随机排列的。

游戏的规则是请同学们快速计算出：如果在这 $N$ 名同学的小组中，取出所有区间长度 $\ge 2$ 的包含连续数的区间，并求出每个区间中第 $2$ 大的数，那么这些数的和最终是多少？

例如有 $4$ 名同学，他们排好队之后，$4$ 个人的年龄分别是 $4, 2, 3, 1$：

• 如果取长度为 $2$ 的区间可以取：$(4,2), (2,3), (3,1)$，这 $3$ 个区间的次大数的和为 $2+2+1=5$；
• 如果取长度为 $3$ 的区间可以取：$(4,2,3), (2,3,1)$，这 $2$ 个区间的次大数的和为 $3+2=5$；
• 如果取长度为 $4$ 的区间可以取：$(4,2,3,1)$，这 $1$ 个区间的次大数的和为 $3$；

因此，所有长度 $\ge 2$ 的包含连续数的区间中的次大数的和为 $5+5+3=13$。

输入格式

• 第一行一个整数 $N$；
• 第二行 $N$ 个整数，这 $N$ 个整数一定是数字 $1 \sim N$ 打乱次序后的结果。

输出格式

输出一个整数，表示所有区间长度 $\ge 2$ 的包含连续数的区间中第 $2$ 大的数的和。

样例

4
4 2 3 1

13

6
1 6 2 4 3 5

50

12
12 1 3 2 10 8 9 7 6 4 5 11

493

数据范围

• 对于 $30\%$ 的数据：$2 \le N \le 100$
• 对于 $100\%$ 的数据：$2 \le N \le 1000$