时空限制

1S/512M

题目描述

给你一个长度为 $n$ 的数组 $a_1, a_2, \dots, a_n$。

你需要求出有多少个子数组（即连续子序列）满足：该子数组中的最大值是最小值的倍数。

形式化地，你需要计算满足 $1 \le l \le r \le n$ 且 $\max(a_l, \dots, a_r) \bmod \min(a_l, \dots, a_r) = 0$ 的数对 $(l, r)$ 的个数。

格式

输入格式

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

第二行 $n$ 个正整数 $a_1,a_2,\cdots a_n$，表示数组 $a$。

输出格式

输出一行一个整数，表示满足条件的子数组个数。

样例

样例输入 #1

4
1 3 2 1

样例输出 #1

9

样例解释 #1

满足条件的子数组如下（用下标区间 $[l, r]$ 表示）：

• $[1, 1]$: 数组为 $\{1\}$，$\max=1, \min=1$，是倍数。
• $[2, 2]$: 数组为 $\{3\}$，$\max=3, \min=3$，是倍数。
• $[3, 3]$: 数组为 $\{2\}$，$\max=2, \min=2$，是倍数。
• $[4, 4]$: 数组为 $\{1\}$，$\max=1, \min=1$，是倍数。
• $[1, 2]$: 数组为 $\{1, 3\}$，$\max=3, \min=1$，是倍数。
• $[2, 3]$: 数组为 $\{3, 2\}$，$\max=3, \min=2$，不是倍数。
• $[3, 4]$: 数组为 $\{2, 1\}$，$\max=2, \min=1$，是倍数。
• $[1, 3]$: 数组为 $\{1, 3, 2\}$，$\max=3, \min=1$，是倍数。
• $[2, 4]$: 数组为 $\{3, 2, 1\}$，$\max=3, \min=1$，是倍数。
• $[1, 4]$: 数组为 $\{1, 3, 2, 1\}$，$\max=3, \min=1$，是倍数。

总计 $9$ 个。

数据规模

对于 $100\%$ 的数据，满足 $1\le n\le 5000$，$1\le a_i\le n$。