Interesting Minimums

As Rares failed his OOP exam mentioned earlier, he tries his luck with this problem hoping to forget his problems. We call an interesting-substring any substring which has at least one minimum value in its second half. $[1, 0, 3, 0, 4, 6]$ is an interesting substring because its minimum, $0$ lays in the second half, while $[1, 0, 3, 0, 5, 6, 8]$ is not an interesting substring as its minimum, $0$ lays in the first half.

$ATTENTION!$ If the substring is of odd length, the middle is considered to be a part of the first half

In this problem, we consider that a substring is a contiguous subset of indices $[i,i+1,\ldots, j-1, j]$.

Given an array of $N$ elements, calculate the number of interesting substrings.

Input data

The first line contains a single number $N$ ($1 \le N \le 200 \ 000$). The second line contains $N$ positive numbers $\le 10^9$ separated with spaces.

Output data

The only line contains the number of substrings computed.

Constraints and clarifications

• For $30$ points $N \leq 200$;
• For another $30$ points, $N \leq 5 \ 000$;
• For the last $40$ points, $N \leq 200 \ 000$.

Example 1

stdin

5
1 3 2 0 5

stdout

6

Example 2

stdin

6
0 0 2 3 1 0

stdout

8

Explanation

For the first example the substrings are: $[(1, 3, 2, 0)$, $(1, 3, 2, 0, 5)$, $(3, 2)$, $(3, 2, 0)$, $(3, 2, 0, 5)$, $(2, 0)]$

For the second example the substrings are: $[(0, 0)$, $(0, 0, 2, 3, 1, 0)$, $(0, 2, 3, 1, 0)$, $(2, 3, 1)$, $(2, 3, 1, 0)$, $(3, 1)$, $(3, 1, 0)$, $(1, 0)]$