整数 $n$ と整数列 $a_1,a_2,\ldots,a_n$ が与えられます。次の条件を満たす整数列 $(b_1,b_2,\ldots,b_n)$ の個数を求めてください。

• 各 $i$ ($1 \le i \le n$) について、$1 \le b_i \le a_i$ である。

• 各 $i$ ($1 \le i \le n-1$) について、$b_i$ は $b_{i+1}$ の約数である。

少なくとも 1 つの位置で値が異なるとき、2 つの列は異なるものとみなします。

このような列の個数は大きくなる可能性があるため、答えを $998\,244\,353$ で割った余りを求めてください。

入力

入力の 1 行目は 1 つの整数 $n$ ($1 \le n \le 200\,000$) からなります。

2 行目は $n$ 個の整数 $a_1,a_2,\ldots,a_n$ ($1 \le a_i \le 200\,000$) からなります。

出力

条件を満たす異なる列の個数を $998\,244\,353$ で割った余りを出力してください。

入出力例

入力 1

2
2 4

出力 1

6

注記

条件を満たす列は、$(2,4)$, $(2,2)$, $(1,4)$, $(1,3)$, $(1,2)$, $(1,1)$ のすべてです。

入力 2

6
265 9801 192168 200000 192018 199809

出力 2

16555779