题目描述

小 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$。