题目描述

在一个遥远的国度里，有一座古老的图书馆，里面收藏着无数珍贵的书籍。这些书籍按照其有趣值被排成了一行，编号从 $1$ 到 $n$，其中第 $i$ 本书的有趣值为 $p_i$，构成了一个排列。

图书馆的管理员小 C 发现，每当有读者来借阅书籍时，他们总是对某个特定范围内的书籍感兴趣，并且这个范围内总是有奇数本书。如果一位读者对于 $[l,r]$ （其中 $1 ≤ l \le r ≤ n$ 且 $r - l$ 为偶数）内的书感兴趣，他会首先选择其中的一本书 $i\in [l,r]$，满足区间 $[l,r]$ 内有趣值小于书 $i$ 与有趣值大于书 $i$ 的书的数量相同（因为他不想一开始就阅读过于无趣的书，也不想过早地阅读最有趣的书）。

为了方便管理图书，小 C 计算了所有（包含奇数本书的）区间 $[l,r]$，读者会选择的第一本书的有趣值 $f_{l,r}$，接着把所有的 $l\times r \times f_{l,r}$ 累加起来，得到检验值。为了验证小 C 的计算是否正确，请你编写代码来计算正确的检验值。

输入格式

第一行包含一个整数 $n$，表示书本的数量。

第二行包含 $n$ 个整数 $p_1,p_2,\cdots,p_n$，表示书的有趣值，构成了一个排列。

输出格式

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

测试样例

Input 1

5
1 5 2 4 3

Output 1

276

Input 2

6
1 2 3 4 5 6

Output 2

714

数据范围与提示

对于全部测试数据，满足 $1\le n \le 10^4$, $p$ 是一个 $1,2,\cdots,n$ 的排列，其中

• 对于 $35\%$ 的测试数据，满足 $n \le 50$
• 对于 $50\%$ 的测试数据，满足 $n\le 400$
• 对于 $75\%$ 的测试数据，满足 $n\le 1000$
• 对于最后的 $5$ 个测试点 $k=1,2,3,4,5$，满足 $n=2000\cdot k$

提示：std 为小常数 $O(n^2)$ 算法，时限为 std 最坏运行时间的十倍以上。