Description

如果一个连续区间 $a_l, a_{l+1}, ..., a_r$ 满足其所有数的乘积大于等于该区间的长度，即 $\prod_{i=l}^r a_i \ge r-l+1$ ，Orange则认为这个区间是积极的。

现在，Orange想请你求出一个长度为 $n$ 的序列 $a_i$ 中，有多少个连续的子区间是积极的。

Format

Input

第一行为一个整数 $n$，表示序列长度。

第二行为 $n$ 个整数 $a_i$，表示给定的序列。

数据范围

$1 \le n \le 5 \times 10^5$

$1 \le a_i \le 10^3$

Output

输出一个整数表示答案。

Samples

3
1 2 3

6

4
1 2 1 2

9

7
1 2 1 2 1 2 1

23

9
2 1 1 1 3 1 1 6 2

32

Limitation

1s, 1024KiB for each test case.