题目描述

给定一个 $N$ 的排列 $P$，对于区间 $[l, r]$，其中 $l < r$，求所有区间 $[l, r]$ 中第二大的数的和。

输入格式

第一行一个整数 $N (2 \le N \le 10^5)$。

第二行 $N$ 个整数 $P_i (1 \le P_i \le N)$。

输出格式

所有区间 $[l, r]$ 中第二大的数的和。

3
2 3 1

5

5
1 2 3 4 5

30

8
8 2 7 3 4 5 6 1

136