GCD Game II

题目描述

小季和小周对上一题的游戏很感兴趣，于是他们也玩起了这个游戏。但是连着几把下来小季都输了，所以小季想找一下这个游戏获胜的诀窍。

小季决定先计算一下一共会有多少个获胜的区间。也就是说，给定一个序列，请你计算其中一共有多少个区间满足区间的最大公约数值不为1。

输入描述

第一行输入一个整数 $n$，代表序列长度。

第二行输入 $n$ 个整数，用空格隔开，代表给定的序列。

输出描述

输出一个整数，代表满足的区间个数。

样例输入1

5
10 3 4 2 8

样例输出1

8

样例1解释

满足条件的子区间有 [10], [3], [4], [4, 2], [4, 2, 8], [2], [2, 8], [8]。

样例输入2

4
2 4 6 8

样例输出2

10

数据范围与约定

对于 $50\%$ 的数据，$1 \le n \le 1000$；

对于 $100\%$ 的数据，$1 \le n \le 10^5$，序列中的每个值 $num$ 满足 $num \in [1, 10^9]$