小 A 正在分析一段连续采集的无线电信号。记录中共有 n 个时刻，第 i 个时刻的信号强度为 p_i。

为了便于比较，所有信号强度恰好组成 1 到 n 的一个排列，因此任意两个时刻的信号强度都不同。

对于任意满足 1\le l < r\le n 的连续时间段 [l,r]，定义 s_{l,r} 为

p_l,p_{l+1},\ldots,p_r

中的第二大值。

小 A 希望衡量所有连续时间段的“次强信号”总量。请你计算

\sum_{l=1}^{n-1}\sum_{r=l+1}^{n}s_{l,r}.

注意，只有长度至少为 2 的时间段才会参与计算。

第一行输入一个整数 n。

第二行输入 n 个整数 p_1,p_2,\ldots,p_n。

输出一行一个整数，表示所有连续时间段的第二大值之和。

样例说明 1

所有长度至少为 2 的连续时间段及其第二大值如下：

因此答案为 1+3+3+1+2+2=12。

样例说明 2

同一个信号强度可能成为许多不同时间段的第二大值，这些贡献都需要分别计算。

数据范围

对于所有测试数据，保证：

• 2\le n\le10^5；
• p_1,p_2,\ldots,p_n 是 1,2,\ldots,n 的一个排列。

本题共 20 个测试点，每个测试点 5 分。

特殊性质 A：序列 p 严格单调递增或严格单调递减。

月赛数学倍增26年8月