该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

谐振之石

题目背景

星空牧羊者 "1zhiO2" 在探索一处古老的宇宙遗迹时，发现了一排神秘的“谐振之石”。这些石头按照一维线性排列，每一块都以其独特的频率进行着微弱的振动。

1zhiO2 发现，如果一段连续的谐振之石拥有一个“共同基频”，它们就会产生共鸣，释放出绚丽的星光。一个石阵序列拥有“共同基频”的条件是，该序列中所有石头的振动频率存在一个大于 1 的公约数。

现在，1zhiO2 记录下了整排谐振之石的频率。它想知道，在这排石头中，总共有多少个连续的“共鸣区段”？

题目描述

给定一个包含 $N$ 个正整数的序列 $a_1, a_2, \dots, a_N$，代表一排谐振之石的振动频率。

一个连续子序列（或称子数组）$[a_l, a_{l+1}, \dots, a_r]$ (其中 $1 \le l \le r \le N$) 被称为一个“共鸣区段”，当且仅当该子序列中所有元素的最大公约数 (GCD) 大于 1。

你的任务是计算给定的序列中，总共有多少个“共鸣区段”。

注意：单个元素组成的子序列 $[a_i]$ 也需要被考虑。其最大公约数就是 $a_i$ 本身。

输入格式

输入第一行包含一个正整数 $N$，表示谐振之石的数量。

输入第二行包含 $N$ 个正整数 $a_1, a_2, \dots, a_N$，用空格分隔，表示每块石头的振动频率。

输出格式

输出一行，包含一个整数，表示“共鸣区段”的总数量。

样例

样例输入 #1

5
2 4 3 6 9

样例输出 #1

9

样例解释

所有满足条件的“共鸣区段”及其最大公约数（GCD）如下：

• 长度为 1 的区段:
  • [2], GCD = 2
  • [4], GCD = 4
  • [3], GCD = 3
  • [6], GCD = 6
  • [9], GCD = 9
• 长度为 2 的区段:
  • [2, 4], GCD = 2
  • [3, 6], GCD = 3
  • [6, 9], GCD = 3
• 长度为 3 的区段:
  • [3, 6, 9], GCD = 3

其他子序列的 GCD 均为 1。例如，gcd(4, 3) = 1，gcd(2, 4, 3) = 1。 总共有 $5 + 3 + 1 = 9$ 个共鸣区段。

提示

数据范围与提示