You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

问题描述

在游戏中中，需要分析玩家自制关卡的节拍数据，找出所有符合“黄金节奏区间”的段落。每个关卡由$n$个节拍点组成，每个节拍点有一个节奏强度值 $a_i$。黄金节奏区间是指一段连续的节拍点，满足该区间内所有节拍点的节奏强度的最大公约数恰好等于该区间的最小节奏强度。

需要计算满足以下条件的整数对 $(l, r)$ 的总个数：

1. $1 \leq l \leq r \leq n$；
2. $\text{gcd}(a_l, a_{l+1}, \dots, a_r) = \min(a_l, a_{l+1}, \dots, a_r)$。

输入格式

• 第一行一个整数 $n(1 \leq n \leq 10^5)$，表示关卡的节拍个数；
• 第二行n个整数 $a_i(1 \leq a_i \leq 10^6)$，表示第i个节拍点的节奏强度。

输出格式

输出一行一个整数，表示“黄金节奏区间”的个数。

输入样例

5
4 6 3 12 2

输出样例

9

样例解释

黄金节奏区间有：$[1, 1], [2, 2], [3, 3], [2, 3], [4, 4], [2, 4], [3, 4], [5, 5], [4, 5]$。

数据分布

$40\%$的数据，$n(1 \leq n \leq 100)$， $a_i(1 \leq a_i \leq 100)$，

$100\%$的数据，$n(1 \leq n \leq 10^5)$， $a_i(1 \leq a_i \leq 10^6)$，

时空限制

• 时间限制：$1s$
• 空间限制：$256M$