← 返回题目列表

Codeforces · 2206/I

I. 生长因子

中文机器翻译题面 查看原题

给定一个整数 $$$n$$$ 和一个整数序列 $$$a_1, a_2, \ldots, a_n$$$。您的任务是确定整数序列 $$$(b_1, b_2, \ldots, b_n)$$$ 的数量,以满足以下条件:

  • $$$1 \leq b_i \leq a_i$$$ 对于每个 $$$i$$$ ($$$1 \le i \le n$$$)。
  • $$$b_i$$$ 是每个 $$$i$$$ ($$$1 \le i \le n-1$$$) 的 $$$b_{i+1}$$$ 的因子。

如果两个序列至少有一个位置不同,则认为它们不同。

由于此类序列的数量可能很大,请以 $$$998\,244\,353$$$ 为模计算答案。

输入

输入的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 200\,000$$$)。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 200\,000$$$)。

输出

输出满足条件的不同序列的数量,以 $$$998\,244\,353$$$ 为模。

示例

输入
复制

2
2 4

输出
复制

6

输入
复制

6
265 9801 192168 200000 192018 199809

输出
复制

16555779

注意

示例输入/输出#1 的说明

以下是满足条件的所有序列:$$$(2,4)$$$、$$$(2,2)$$$、$$$(1,4)$$$、$$$(1,3)$$$、$$$(1,2)$$$ 和 $$$(1,1)$$$。