题目描述

You are given an integer $n$ and a sequence of integers $a_1, a_2, \ldots, a_n$ . Your task is to determine the number of integer sequences $(b_1, b_2, \ldots, b_n)$ such that the following conditions are satisfied:

• $1 \leq b_i \leq a_i$ for each $i$ ( $1 \le i \le n$ ).
• $b_i$ is a factor of $b_{i+1}$ for each $i$ ( $1 \le i \le n-1$ ).

Two sequences are considered different if they differ in at least one position.

Since the number of such sequences may be large, compute the answer modulo $998\,244\,353$ .

输入格式

The first line of input contains a single integer $n$ ( $1 \le n \le 200\,000$ ).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ( $1 \le a_i \le 200\,000$ ).

输出格式

Output the number of distinct sequences satisfying the conditions, modulo $998\,244\,353$ .

2
2 4

6

6
265 9801 192168 200000 192018 199809

16555779

提示

Explanation for the sample input/output #1

The following are all sequences satisfying the conditions: $(2,4)$ , $(2,2)$ , $(1,4)$ , $(1,3)$ , $(1,2)$ , and $(1,1)$ .