No testdata at current.

时间限制： 1.0 秒

空间限制： 512 MB

题目描述

Alice 最近对计数问题产生了浓厚的兴趣，尤其是有关连续子区间的性质。现在，她面前有一个长为 $n$ 的正整数序列 $a_1,a_2,\cdots,a_n$，她想统计有多少个连续子区间 $[l,r]\ (1\le l\le r\le n)$，满足区间乘积大于等于区间长度，即 $\prod\limits_{k=l}^r a_k\ge r-l+1$。当序列长度较大时，手动计算将会变得十分麻烦，因此她想请你帮助计算合法子区间的数目。

输入格式

从标准输入读入数据。

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

第二行包含 $n$ 个正整数 $a_1,a_2,\cdots,a_n$，表示给定的序列。

输出格式

输出到标准输出。

输出一个整数，表示满足条件的子区间数量。结果可能较大，请使用 64 位整数类型进行存储。

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

子任务

对于所有数据，$1\le n\le 5\times 10^5,\ 1\le a_i\le 10^3$。