Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

combinatorics

number theory

sortings

*1500

No tag edit access

The problem statement has recently been changed. View the changes.

×
B. Effects of Anti Pimples

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputChaneka has an array $$$[a_1,a_2,\ldots,a_n]$$$. Initially, all elements are white. Chaneka will choose one or more different indices and colour the elements at those chosen indices black. Then, she will choose all white elements whose indices are multiples of the index of at least one black element and colour those elements green. After that, her score is the maximum value of $$$a_i$$$ out of all black and green elements.

There are $$$2^n-1$$$ ways for Chaneka to choose the black indices. Find the sum of scores for all possible ways Chaneka can choose the black indices. Since the answer can be very big, print the answer modulo $$$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$$$.

Examples

Input

4 19 14 19 9

Output

265

Input

1 0

Output

0

Input

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

Output

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$$$.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/02/2023 04:23:13 (i1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|