You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

时间限制： 1.0 秒

空间限制： 512 MB

题目背景

西西艾弗岛上弗艾西西大学的同学们正在集体锻炼。

题目描述

现在一共有 $n$ 个弗艾西西大学的同学站成一排，同学们的体魄各有不同，第 $i$ 个同学具有力量值 $a_i$。

在集体锻炼的过程中，老师会指定队列中连续一段同学，让他们协作完成一项运动。这项运动的强度由这些同学的力量值决定，具体而言，假设老师选择了第 $l$ 到第 $r$ 个同学，所进行运动的强度就是 $\gcd(a_l,a_{l+1},\dots,a_r)$，其中 $\gcd$ 表示最大公约数。特别地，当 $l=r$ 时，我们认为运动的强度就等于 $a_l$。

基于以上的事实，老师规定对一个区间 $[l,r]$，它的体育价值 $f([l,r])=l\times r\times \gcd(a_l,a_{l+1},\dots,a_r)$。

老师想求所有区间的体育价值之和，即 $\sum\limits_{l=1}^n\sum\limits_{r=l}^nf([l,r])$。

因为人实在太多了，老师不能自己算，于是希望你能帮他写一个程序来计算。如果你写出这个程序，他就会给你加平时分。答案很大，你只需要求出其对 $998244353$ 取模的结果即可。

输入格式

从标准输入读入数据。

输入的第一行为一个整数 $n$，表示同学的数量。

接下来一行 $n$ 个整数 $a_1,a_2,\dots ,a_n$，代表 $n$ 个同学的力量值。

输出格式

输出到标准输出。

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

5
10 2 6 6 8

586

20
7 6 5 5 17 18 13 3 11 12 7 9 16 15 5 19 20 13 14 6

57254

子任务

对于所有数据，保证 $1\le n,a_i\le 10^6$。

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。