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$,为所给的数列。

输出格式


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

输入输出样例

输入样例 #1

4
1 3 9 3

输出样例 #1

5

输入样例 #2

5
1 1 2 1 1

输出样例 #2

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