题目描述

水晶在一座古堡中发现了一排石碑，石碑从左到右有 $n$ 块，每块石碑都印有一个正整数 $a_i$。

每次收集能量时可以选择两块石碑 $i, j$ ($1 \leq i \leq j \leq n$)，这样可以收集到 $\gcd{(a_i, a_{i + 1}, a_{i + 2}, \cdots, a_j)}^{\text{*}}$ 点能量。

你有无限次选择机会，但每对 $(i, j)$ 最多可被选择一次。现在你想知道你最多能获得多少点能量？这个答案可能很大，请把答案对 $998244353$ 取模后输出。

$^{\text{*}}$ $\gcd$ 是指最大公约数。

输入格式

第一行包含一个整数 $n$ ($1 \leq n \leq 2 \cdot 10^5$) — 石碑的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \leq a_i \leq 10^9$) — 每个石碑上的数字。

输出格式

输出一个整数，表示最大能获得的能量对 $998244353$ 取模后的结果。

样例

4
2 4 6 3

26

8
6 6 9 3 12 15 21 3

162