题目描述

小姜 厌倦了求解最大值，因此，王老师 给 小姜 出了一个次大值问题。

王老师 会给 小姜 一个 1∼n 每个数各出现一次的排列，$a_1 ,a_2​ ,…,a_n​$ ，并且给定一个定义 $f(l,r)$ 表示区间 $[l,r]$，即 $a_l​ ,a_{l+1}​ ,…,{a_r}$​ 中的次大值。

王老师 要求 小姜 求出 $∑f(l,r)$，其中 $1≤l<r≤n$，即对排列中的所有区间 $[l,r]$ 的次大值进行求和。

现在，小姜 将这个难题交给了你。

输入格式

第一行一个整数 n，表示整数个数。

第二行共 n 个整数，$a_1​ ,a_2 ,…,a_n$ 表示一个排列。

输出格式

一行一个整数，表示答案。

样例输入 1

3
2 3 1

样例输出 1

5

样例输入 2

8
8 2 7 3 4 5 6 1

样例输出 2

136

提示/说明

样例 1 解释

区间 $[1,2],[1,3]$ 的次大值是 $2$，区间 $[2,3]$ 的次大值是 $1$，对所有区间的次大值求和为 $2+2+1=5$。

数据范围

对于 30% 的数据，满足 $n≤100$；

对于 60% 的数据，满足 $n≤5000$；

对于 100% 的数据，满足 $n≤10^5$ 。