给定一个长度为 $n$ 的序列 $(s_1, s_2, \ldots, s_n)$。函数 $f$ 的定义如下：

$$f(i, j, k) = \begin{cases} 1 & \text{if } s_{i + t} \leq s_{j + t} \text{ for all } 0 \leq t < k \\ 0 & \text{otherwise} \end{cases}$$

输出以下和的值： $$\sum_{i = 1}^{n}\sum_{j = 1}^{n}\sum_{k = 1}^{\min(n-i+1,n-j+1)}f(i,j,k)\text{.}$$

输入格式

第一行包含一个整数 $n$，表示序列的长度（$1 \leq n \leq 5000$）。

第二行包含 $n$ 个整数 $s_1, s_2, \ldots, s_n$，表示序列本身（$1 \le s_i \le 10^9$）。

输出格式

输出该问题的答案。

样例

样例输入 1

2
2 3

样例输出 1

4

样例输入 2

5
2 4 2 2 1

样例输出 2

35

说明

在第一个样例中：

• $f(1,1,1) = 1$
• $f(1,1,2) = 1$
• $f(1,2,1) = 1$
• $f(2,1,1) = 0$
• $f(2,2,1) = 1$