F. 跬步千里
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

对于正整数 $$$m$$$、$$$X$$$、$$$Y$$$，定义如下过程：

初始时，有 $$$m$$$ 个整数点 $$$P_1, P_2, \ldots, P_m$$$ 位于 $$$(0, 0)$$$，以及一个整数点 $$$P_{m + 1}$$$ 位于 $$$(X, Y)$$$。记点 $$$P_i$$$ 的坐标为 $$$(x_{P_i}, y_{P_i})$$$。

你可以进行若干次（包括零次）操作。每次操作选择一个整数 $$$k$$$（$$$2 \le k \le m$$$），将点 $$$P_k$$$ 向 $$$x$$$ 轴正方向或 $$$y$$$ 轴正方向移动 $$$1$$$ 个单位长度。每次操作后，必须满足：对于所有 $$$1 \le i \le j \le m + 1$$$，都有 $$$x_{P_i} \le x_{P_j}$$$ 且 $$$y_{P_i} \le y_{P_j}$$$。

定义这 $$$m + 1$$$ 个点的「价值」为下标相邻的两点的曼哈顿距离的最小值，即： $$$$$$ \min \limits_{1 \le i \le m} \left( \left| x_{P_{i + 1}} - x_{P_i} \right| + \left| y_{P_{i + 1}} - y_{P_i} \right| \right) $$$$$$

令 $$$F(m, X, Y)$$$ 表示经过若干次操作后能够得到的最大「价值」。

给定一个长度为 $$$n$$$ 的正整数序列 $$$a_1, a_2, \ldots, a_n$$$，请你求出 $$$\sum \limits_{1 \le j \le i \le n} F(i, a_i, a_j)$$$ 的值。

Input

第一行一个整数 $$$n$$$（$$$1 \le n \le 10^5$$$），表示序列的长度。

第二行 $$$n$$$ 个整数 $$$a_1, a_2, \ldots, a_n$$$（$$$1 \le a_i \le 10^5$$$），表示给定的序列。

Output

仅一行，包含一个整数，表示你的答案。

Example
Input
6
1 1 4 5 1 4
Output
19
Note

样例中 $$$n = 6$$$，$$$a = [1, 1, 4, 5, 1, 4]$$$。

当 $$$i = 1$$$，$$$j = 2$$$ 时，求和项为 $$$F(2, 1, 1)$$$：初始时 $$$P_1 = P_2 = (0, 0)$$$，$$$P_3 = (1, 1)$$$；将 $$$P_2$$$ 向 $$$x$$$ 轴正方向移动 $$$1$$$ 个单位长度，此时 $$$P_2 = (1, 0)$$$，下标相邻的两点的曼哈顿距离分别为 $$$1$$$ 和 $$$1$$$，「价值」为 $$$1$$$。可以证明无法得到更大的「价值」，因此 $$$F(2, 1, 1) = 1$$$。

将所有求和项累加，可以证明答案是 $$$19$$$。