406555: GYM102439 I Equal Mod Segments

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

I. Equal Mod Segmentstime limit per test1.5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard 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.

ExamplesInput
2
5 5
Output
3
Input
3
8 3 5
Output
4

加入题单

上一题 下一题 算法标签: