Problem Description

Xiao D has a sequence $\{a\}$. A pair $(i, j)$ (where $i \le j$) is considered beautiful 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$. You are asked to 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$, which are the elements of the sequence.

Output Format

Output a single integer, which is the count of beautiful pairs.

Sample Input and Output

Sample Input #1

4
1 3 9 3

Sample Output #1

5

Sample Input #2

5
1 1 2 1 1

Sample Output #2

14

Notes

[Sample Explanation #1]

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

[Sample Explanation #2]

Only the pair $(3,3)$ is not feasible.

[Data Range]

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

见题面 Input 部分

见题面 Output 部分