Counting Beautiful Pairs

We define a sequence ({a}). A pair ((i,j)) (with (1 \le i \le j \le n)) is considered beautiful if the product (a_i \times a_j) is not greater than the maximum element in the subarray (a_i, a_{i+1}, \ldots, a_j); that is, [ a_i \times a_j \leq \max{a_i, a_{i+1}, \ldots, a_j}. ] Given the sequence, count the number of beautiful pairs.

inputFormat

The first line contains a single integer (n) — the length of the sequence. The second line contains (n) space-separated integers (a_1, a_2, \ldots, a_n).

outputFormat

Output a single integer representing the number of beautiful pairs.

sample

3
0 1 2

5