You are given a sequence $(s_1, s_2, \ldots, s_n)$ of length $n$. The function $f$ is defined as follows:

$$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}$$

Print the value of the following sum: $$\sum_{i = 1}^{n}\sum_{j = 1}^{n}\sum_{k = 1}^{\min(n-i+1,n-j+1)}f(i,j,k)\text{.}$$

Input

The first line contains an integer $n$, the length of the sequence ($1 \leq n \leq 5000$).

The second line contains $n$ integers $s_1, s_2, \ldots, s_n$: the sequence itself ($1 \le s_i \le 10^9$).

Output

Print the answer to the problem.

Examples

Input 1

2
2 3

Output 1

4

Input 2

5
2 4 2 2 1

Output 2

35

Note

In the first example:

• $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$