I. Equal Mod Segments
time limit per test
1.5 s
memory limit per test
256 megabytes
input
standard input
output
standard output

Given an array $$$a_1, a_2, \dots, a_n$$$, consisting of $$$n$$$ positive integers. You need to find a number of pairs $$$(L, R)$$$ (where $$$L \le R$$$) such that the following condition holds: $$$a_L \bmod a_{L+1} \bmod \dots \bmod a_R = a_R \bmod\ a_{R-1} \bmod \dots \bmod a_L$$$, where $$$\bmod$$$ is defined as operation of taking the remainder of the division.

Input

The first line contains an integer $$$n$$$  — the size of the array.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$  — the elements of the array.

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

$$$1 \le a_i \le 3 \cdot 10^5$$$

Output

Print a single integer  — number of pairs $$$(L, R)$$$, satisfying the given condition.

Examples
Input
2
5 5
Output
3
Input
3
8 3 5
Output
4