A. 最大公约数与和
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

给定一个长度为 $$$n$$$ 的数组 $$$a$$$， 第 $$$i$$$ 个元素 为 $$$a_i$$$， 定义 $$$gcd(l ,r)$$$ 为 $$$a$$$ 数组中下标在 $$$[l, r]$$$ 中的所有数的最大公约数， $$$sum(l, r)$$$ 为 在 $$$a$$$ 数组中下标在 $$$[l, r]$$$ 中的所有数的和。

你要找到满足 $$$gcd(l, r) \le sum(l, r)$$$ 的所有区间的个数。

Input

第一行有一个正整数 $$$n~ (n \le 10^5)$$$ ，第二行有 $$$n$$$ 个正整数， $$$a_i~(a_i \le 10^9)$$$ 。

Output

输出一个整数，表示满足条件的区间个数。

Example
Input
3
1 1 2
Output
3