Description

谷歌翻译

Chaneka 有一个数组 $[a_1,a_2,\ldots,a_n]$ 。最初，所有元素都是白色的。 Chaneka 将选择一个或多个不同的索引，并将这些所选索引处的元素涂成黑色。然后，她将选择索引是至少一个黑色元素索引的倍数的所有白色元素，并将这些元素着色为绿色。之后，她的分数就是所有黑色和绿色元素中 $a_i$ 的最大值。

Chaneka 有 $2^n-1$ 种选择黑色索引的方法。求 Chaneka 选择黑色指数的所有可能方式的分数总和。由于答案可能非常大，因此请打印对 $998\,244\,353$ 取模的答案。

Input

The first line contains a single integer $n$ ($1 \leq n \leq 10^5$) — the size of array $a$.

The second line contains $n$ integers $a_1,a_2,a_3,\ldots,a_n$ ($0\leq a_i\leq10^5$).

Output

An integer representing the sum of scores for all possible ways Chaneka can choose the black indices, modulo $998\,244\,353$.

4
19 14 19 9

1
0

15
90000 9000 99000 900 90900 9900 99900 90 90090 9090 99090 990 90990 9990 99990

265

0

266012571

Note

In the first example, below are the $15$ possible ways to choose the black indices:

• Index $1$ is black. Indices $2$, $3$, and $4$ are green. Maximum value among them is $19$.
• Index $2$ is black. Index $4$ is green. Maximum value among them is $14$.
• Index $3$ is black. Maximum value among them is $19$.
• Index $4$ is black. Maximum value among them is $9$.
• Indices $1$ and $2$ are black. Indices $3$ and $4$ are green. Maximum value among them is $19$.
• Indices $1$ and $3$ are black. Indices $2$ and $4$ are green. Maximum value among them is $19$.
• Indices $1$ and $4$ are black. Indices $2$ and $3$ are green. Maximum value among them is $19$.
• Indices $2$ and $3$ are black. Index $4$ is green. Maximum value among them is $19$.
• Indices $2$ and $4$ are black. Maximum value among them is $14$.
• Indices $3$ and $4$ are black. Maximum value among them is $19$.
• Indices $1$, $2$, and $3$ are black. Index $4$ is green. Maximum value among them is $19$.
• Indices $1$, $2$, and $4$ are black. Index $3$ is green. Maximum value among them is $19$.
• Indices $1$, $3$, and $4$ are black. Index $2$ is green. Maximum value among them is $19$.
• Indices $2$, $3$, and $4$ are black. Maximum value among them is $19$.
• Indices $1$, $2$, $3$, and $4$ are black. Maximum value among them is $19$.

The total sum is $19+14+19+9+19+19+19+19+14+19+19+19+19+19+19 = 265$.

deepl翻译

在第一个示例中，以下是选择黑色索引的可能方法： $15$ ：

• 索引 $1$ 为黑色。索引 $2$ 、 $3$ 和 $4$ 为绿色。其中最大值为 $19$ 。
• 索引 $2$ 为黑色。索引 $4$ 为绿色。其中最大值为 $14$ 。
• 索引 $3$ 为黑色。其中最大值为 $19$ 。
• 索引 $4$ 为黑色。其中最大值为 $9$ 。
• 索引 $1$ 和 $2$ 为黑色。索引 $3$ 和 $4$ 为绿色。其中最大值为 $19$ 。
• 索引 $1$ 和 $3$ 为黑色。索引 $2$ 和 $4$ 为绿色。其中最大值为 $19$ 。
• 索引 $1$ 和 $4$ 为黑色。索引 $2$ 和 $3$ 为绿色。其中最大值为 $19$ 。
• 索引 $2$ 和 $3$ 为黑色。索引 $4$ 为绿色。其中最大值为 $19$ 。
• 索引 $2$ 和 $4$ 为黑色。其中最大值为 $14$ 。
• 索引 $3$ 和 $4$ 为黑色。其中最大值为 $19$ 。
• 索引 $1$ 、 $2$ 和 $3$ 为黑色。索引 $4$ 为绿色。其中最大值为 $19$ 。
• 索引 $1$ 、 $2$ 和 $4$ 为黑色。索引 $3$ 为绿色。其中最大值为 $19$ 。
• 索引 $1$ 、 $3$ 和 $4$ 为黑色。索引 $2$ 为绿色。其中最大值为 $19$ 。
• 索引 $2$ 、 $3$ 和 $4$ 为黑色。其中最大值为 $19$ 。
• 索引 $1$ 、 $2$ 、 $3$ 和 $4$ 为黑色。其中最大值为 $19$ 。

总和为 $19+14+19+9+19+19+19+19+14+19+19+19+19+19+19 = 265$ 。