给定一个长度为$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}$
