“互质序列”非常容易找到，但是我们可以尝试通过删除这个序列的一个非空连续子序列来扩大它的最大公约数。

现在给定一个长度为 $n$ 的序列 $a_i$ ，你需要从中删除一个非空连续子序列，使得剩下至少2个数，令 $E$ 为剩下数的最大公约数的期望值，$S$ 为合法的方案数，请计算 $E*S$ 的值。因为这个值可能非常大，请对998244353取模输出。

##输入格式

第一行包含一个正整数 $n \ (3 \le n \le 10^5)$ ，表示序列的长度。

第二行包含n个正整数 $a_i \ (1 \le a_i \le 10^9)$，分别表示序列中的每个元素。

输出格式

输出一行一个整数，即E*S mod 998244353的值。

样例输入

5
3 4 5 2 9

样例输出

14