Beautiful Pair

小 D 有个数列 $\{a\}$，当一个数对 $(i,j)$（$i \le j$）满足 $a_i$ 和 $a_j$ 的积不大于 $a_i, a_{i+1}, \ldots, a_j$ 中的最大值时，小 D 认为这个数对是美丽的。请你求出美丽的数对的数量。

第一行输入一个整数 $n$，表示元素个数。 第二行输入 $n$ 个整数 $a_1,a_2,a_3,\ldots,a_n$，为所给的数列。

输出一个整数，为美丽的数字对数。

4
1 3 9 3

5

5
1 1 2 1 1

14

**【样例解释 #1】** 五种可行的数对为 $(1,1), (1,2), (1,3), (1,4), (2,4)$。 **【样例解释 #2】** 只有数对 $(3,3)$ 不可行。 **【数据范围】** 对于 $100 \%$ 的数据，$1\le n\le{10}^5$，$1\le a_i\le{10}^9$。