Description

Xiao D has a sequence $\{a\}$. For a pair $(i, j)$ ($i \le j$), if the product of $a_i$ and $a_j$ is not greater than the maximum value among $a_i, a_{i+1}, \ldots, a_j$, then Xiao D considers this pair to be beautiful. Please find the number of beautiful pairs.

Input Format

The first line contains an integer $n$, representing the number of elements.
The second line contains $n$ integers $a_1, a_2, a_3, \ldots, a_n$, representing the given sequence.

Output Format

Output one integer, the number of beautiful pairs.

4
1 3 9 3

5

5
1 1 2 1 1

14

Hint

[Sample Explanation #1]

The five valid pairs are $(1,1), (1,2), (1,3), (1,4), (2,4)$.

[Sample Explanation #2]

Only the pair $(3,3)$ is invalid.

[Constraints]

For $100\%$ of the testdata, $1 \le n \le 10^5$, and $1 \le a_i \le 10^9$.

Translated by ChatGPT 5