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

时间限制：1000ms　内存限制：512MB

结果比较方式为全文比较（过滤行末空格及文末换行）。

题目描述

某材料实验室对一批样品进行连续检测。每个样品检测后得到一个正整数检测值，实验室按检测顺序把当天全部检测值记录为一条检测序列，记为 $a_1, a_2, \dots, a_n$。

技术人员的检测报告里，对一段连续区间 $[l, r]$（$1 \le l \le r \le n$）定义了一个指标凝聚值：区间内所有检测值的最大公约数 × 区间长度，即 $\gcd(a_l, a_{l+1}, \dots, a_r) \times (r - l + 1)$。

现在实验室需要对整条序列做一次工艺稳定性评估，请把序列上全部 $\frac{n(n+1)}{2}$ 个连续区间的凝聚值累加，输出累加结果对 $998244353$ 取模后的值。

输入格式

从文件 gcd.in 中读入数据。

• 第一行一个正整数 $n$，表示检测序列的长度。
• 第二行 $n$ 个正整数 $a_1, a_2, \dots, a_n$，表示按检测顺序记录的检测值。

输出格式

输出到文件 gcd.out 中。

输出一行一个整数，表示所有区间凝聚值之和对 $998244353$ 取模的结果。

样例

样例 1 输入

3
6 4 8

样例 1 输出

36

样例 1 解释

共 $6$ 个区间，逐个计算：

• $[1,1]$：$\gcd(6)=6$，长度 $1$，凝聚值 $6$；
• $[1,2]$：$\gcd(6,4)=2$，长度 $2$，凝聚值 $4$；
• $[1,3]$：$\gcd(6,4,8)=2$，长度 $3$，凝聚值 $6$；
• $[2,2]$：$\gcd(4)=4$，长度 $1$，凝聚值 $4$；
• $[2,3]$：$\gcd(4,8)=4$，长度 $2$，凝聚值 $8$；
• $[3,3]$：$\gcd(8)=8$，长度 $1$，凝聚值 $8$。

相加得 $6+4+6+4+8+8=36$。

样例 2 输入

4
12 6 9 3

样例 2 输出

84

样例 2 解释

例如区间 $[1,3]$：$\gcd(12,6,9)=3$，长度 $3$，凝聚值 $9$；区间 $[2,3]$：$\gcd(6,9)=3$，长度 $2$，凝聚值 $6$；区间 $[4,4]$：$\gcd(3)=3$，长度 $1$，凝聚值 $3$。全部 $10$ 个区间的凝聚值相加得 $84$。

样例 3 输入

5
100 50 25 30 15

样例 3 输出

580

样例 3 解释

例如区间 $[1,5]$：$\gcd(100,50,25,30,15)=5$，长度 $5$，凝聚值 $25$；区间 $[4,5]$：$\gcd(30,15)=15$，长度 $2$，凝聚值 $30$。全部 $15$ 个区间的凝聚值相加得 $580$。

数据范围

对于所有测试数据，保证：

• $1 \le n \le 10^5$；
• $1 \le a_i \le 10^9$。

各测试点的约束如下：

无特殊性质。