C-简单序列题_牛客挑战赛86

时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 小 K 有一个长度为 $n$ 的序列 $a_1,a_2,\dots,a_n$ 。
$\hspace{15pt}$ 小 K 喜欢 $\mathrm{MEX}$ ，他定义 $\mathrm{MEX}(\Bbb S)$ 为最小的没有在 $\Bbb S$ 集合中出现的且大于 $0$ 的自然数。形式化地， $\mathrm{MEX}(\Bbb S) = \min\limits_{x\notin \Bbb S,\ x\ge 1}x$ 。

$\hspace{15pt}$ 小 K 定义区间 $[l,r] \left(1\le l\le r\le n\right)$ 的美丽度为 $f(l,r) = \mathrm{MEX}\Big(\Big\{a_l,\gcd(a_l,a_{l+1}),\dots,\gcd(a_l,a_{l+1},\dots,a_r )\Big\}\Big)$ 。
$\hspace{15pt}$ 小 K 想要知道序列 $a$ 中 $\tfrac{n(n+1)}{2}$ 个连续子区间的美丽度之和，他想请你来帮他算一算。

【名词解释】
$\hspace{15pt}$ 最大公约数（gcd）：指两个或多个整数共有约数中最大的一个。例如， $12$ 和 $30$ 的公约数有 $1,2,3,6$ ，其中最大的约数是 $6$ ，因此记作 $\gcd(12,30)=6$ 。

输入描述:

第一行输入一个整数 ，表示序列的长度。
第二行输入  个整数 ，表示序列中的元素。

输出描述:

输出一个整数，表示全部连续子区间的美丽度之和。

示例1

输入

复制

5
3 2 1 2 3

输出

复制

示例2

输入

复制

3
1 3 2

输出

复制

示例3

输入

复制

2
5 3

输出

复制

备注:

在几乎全部的情况下，PyPy 的运行速度优于 Python，我们建议您选择对应版本的 PyPy 进行提交、而不是 Python。