当前没有测试数据。

题目描述

给定一个1，2，...，N  的排列 P$_1$,P$_2$, ... P$_N$，对于所有长度大于 1 的区间[l, r]，即 l<r，必然存在第二大的数。

对所有长度大于 1 的区间[l, r]中第二大的数，求和。

输入格式

第一行输入一个正整数 N

第二行输入排列 P$_1$,P$_2$, ... P$_N$

输出格式

输出答案

样例

输入输出样例

输入样例#1

3
2 3 1

输出样例#1

5

输入样例#2

5
1 2 3 4 5

输出样例#2

30

输入样例#3

8
8 2 7 3 4 5 6 1

输出样例#3

136

数据范围与提示

• 2<=N<=10$^5$
• 1<=P$_i$<=N
• P$_i$!=P$_j$(i!=j)
• 输入数据均为整数