410284: GYM103999 M 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,\cdots j-1, j]$$$.

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

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

The only line contains the number of substrings computed.

• for 30 points $$$N \leq 200$$$
• for another 30 points, $$$N \leq 5000$$$
• for the last 40 points, $$$N \leq 200000$$$

5
1 3 2 0 5

6

6
0 0 2 3 1 0

8

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)]$$$