Growth Factor

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 \le b_i \le 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\).

Input

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

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

2
2 4

6

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)\).

6
265 9801 192168 200000 192018 199809

16555779