UOJ Logo Zijian Online Judge

ZOJ

#5. 计算数列

Statistics

给定一个长度为$N$的数列$A$。

设$Max(l,r)=Max(A_l,A_{l+1},…,A_r)$,$Gcd(l,r)=gcd(A_l,A_{l+1},…,A_r)$。

求$\sum_{l=1}^{N}\sum_{r=l}^{N}Max(l,r)*Gcd(l,r)$对$998244353$取模的结果。

输入格式

第一行为$1$个正整数$N$。

第二行为$N$个正整数$A_i$。

输出格式

输出答案对$998244353$取模的结果。

样例

input

6
2 4 6 3 8 4

output

303

限制与约定

对于 $30\texttt{%}$ 的数据,$1 \leq N \leq 1000$。

对于另外 $20\texttt{%}$ 的数据,保证数列$A$由$N$个互不相同的质数组成。

对于另外 $20\texttt{%}$ 的数据,保证数列$A$为随机生成。

对于 $100\texttt{%}$ 的数据,$1 \leq N \leq 152501$,$1 \leq A_i \leq 10^9$。

时间限制:$1\texttt{s}$

空间限制:$128\texttt{MB}$