Effects of Anti Pimples
Contest: Codeforces Round 902 (Div. 1, based on COMPFEST 15 - Final Round)
Difficulty rating: 1500
Tags: combinatorics, number theory, sortings

Chaneka 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 format:
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 format:
An integer representing the sum of scores for all possible ways Chaneka can choose the black indices, modulo $$$998\,244\,353$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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

Example input:
4
19 14 19 9

Example output:
265

Example input:
1
0

Example output:
0

Editorial:
For some value $$$w$$$, let $$$f(w)$$$ be the number of different ways to choose the black indices such that the score is exactly $$$w$$$ and let $$$g(w)$$$ be the number of different ways to choose the black indices such that the score is at most $$$w$$$. Then $$$f(w) = g(w) - g(w-1)$$$.
Let's try to calculate $$$g(w)$$$. First, group the elements in $$$a$$$ into two groups, with group 1 containing elements with values greater than $$$w$$$ and group 2 containing elements with values not greater than $$$w$$$. Notice that the only requirement we must satisfy is to not make any group 1 element black or green and we can do anything to the group 2 elements. In order to make sure that no group 1 element is black or green, we must make sure that no black index we choose is a factor of at least one group 1 index. This means, we just need calculate some value $$$c$$$ that represents the number of different indices that is a factor at least one group 1 index, then the value of $$$g(w)$$$ is $$$2^{n-c}-1$$$.
The answer to the original problem is the sum of $$$f(w)\cdot w$$$ for all possible values $$$w$$$. However, we just care about the values $$$w$$$ such that $$$f(w)\neq0$$$, which only happens if $$$w$$$ is equal to the value of some element of $$$a$$$.
In order to calculate $$$g(w)$$$ for all desired values of $$$w$$$, we need to iterate the elements of $$$a$$$ from the biggest value to the smallest value. Each element we iterate, we iterate every index that is a factor of the index of the current element and mark those indices as group 1 while we keep track of the value of $$$c$$$.
The total number of iterations is the total number of factors for every index, which is $$$n\log n$$$.
Time Complexity: $$$O(n\log n)$$$