题目描述

有 $N$ 名同学站成一排，他们的年龄恰好是 $1$ 到 $N$，每个年龄出现一次。

对于队伍中每一段长度不小于 $2$ 的连续区间，找出该区间内第二大的年龄。请计算所有这些第二大年龄之和。

输入格式

第一行包含一个整数 $N$，表示同学人数。

第二行包含 $N$ 个整数 $a_1,a_2,\ldots,a_N$，表示同学从左到右的年龄。输入保证它们是 $1$ 到 $N$ 的一个排列。

输出格式

输出一个整数，表示所有长度不小于 $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

样例解释

样例 1 中，长度为 $2$、$3$、$4$ 的连续区间的第二大年龄之和分别为 $5$、$5$、$3$，总和为 $13$。

数据范围与提示

• $2 \le N \le 1000$
• $a_1,a_2,\ldots,a_N$ 是 $1$ 到 $N$ 的一个排列