Interesting Minimums

Time limit: 1s Memory limit: 256MB Input: Output:

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][1, 0, 3, 0, 4, 6] is an interesting substring because its minimum, 00 lays in the second half, while [1,0,3,0,5,6,8][1, 0, 3, 0, 5, 6, 8] is not an interesting substring as its minimum, 00 lays in the first half.

ATTENTION!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,,j1,j][i,i+1,\ldots, j-1, j].

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

Input data

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

Output data

The only line contains the number of substrings computed.

Constraints and clarifications

  • For 3030 points N200N \leq 200;
  • For another 3030 points, N5 000N \leq 5 \ 000;
  • For the last 4040 points, N200 000N \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), (1,3,2,0,5)(1, 3, 2, 0, 5), (3,2)(3, 2), (3,2,0)(3, 2, 0), (3,2,0,5)(3, 2, 0, 5), (2,0)](2, 0)]

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

Log in or sign up to be able to send submissions!