P4755 Beautiful Pair

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.

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 one integer, the number of beautiful pairs.

**[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