题目描述

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

游戏的规则是请同学们快速计算出：如果在这N名同学的小组中，取出所有区间长度≥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；

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

输入格式

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

输出格式

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

样例输入 1

4
4 2 3 1

样例输出 1

13

样例输入 2

6
1 6 2 4 3 5

样例输出 2

50

样例输入 3

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

样例输出 3

493

数据范围

• 对于30%的数据，保证2 ≤ N ≤ 100；
• 对于100%的数据，保证2 ≤ N ≤ 1000。