Extreme Extension
Contest: Codeforces Round 752 (Div. 1)
Difficulty rating: 2300
Tags: dp, greedy, math, number theory

For an array $$$b$$$ of $$$n$$$ integers, the extreme value of this array is the minimum number of times (possibly, zero) the following operation has to be performed to make $$$b$$$ non-decreasing:

- Select an index $$$i$$$ such that $$$1 \le i \le |b|$$$, where $$$|b|$$$ is the current length of $$$b$$$.
- Replace $$$b_i$$$ with two elements $$$x$$$ and $$$y$$$ such that $$$x$$$ and $$$y$$$ both are positive integers and $$$x + y = b_i$$$.
- This way, the array $$$b$$$ changes and the next operation is performed on this modified array.

For example, if $$$b = [2, 4, 3]$$$ and index $$$2$$$ gets selected, then the possible arrays after this operation are $$$[2, \underline{1}, \underline{3}, 3]$$$, $$$[2, \underline{2}, \underline{2}, 3]$$$, or $$$[2, \underline{3}, \underline{1}, 3]$$$. And consequently, for this array, this single operation is enough to make it non-decreasing: $$$[2, 4, 3] \rightarrow [2, \underline{2}, \underline{2}, 3]$$$.

It's easy to see that every array of positive integers can be made non-decreasing this way.

YouKn0wWho has an array $$$a$$$ of $$$n$$$ integers. Help him find the sum of extreme values of all nonempty subarrays of $$$a$$$ modulo $$$998\,244\,353$$$. If a subarray appears in $$$a$$$ multiple times, its extreme value should be counted the number of times it appears.

An array $$$d$$$ is a subarray of an array $$$c$$$ if $$$d$$$ can be obtained from $$$c$$$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10\,000$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$).

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^5$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$10^5$$$.

Output format:
For each test case, print a single integer  — the sum of extreme values of all subarrays of $$$a$$$ modulo $$$998\,244\,353$$$.

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

Note:
Let $$$f(l, r)$$$ denote the extreme value of $$$[a_l, a_{l+1}, \ldots, a_r]$$$.

In the first test case,

- $$$f(1, 3) = 3$$$, because YouKn0wWho can perform the following operations on the subarray $$$[5, 4, 3]$$$ (the newly inserted elements are underlined):$$$[5, 4, 3] \rightarrow [\underline{3}, \underline{2}, 4, 3] \rightarrow [3, 2, \underline{2}, \underline{2}, 3] \rightarrow [\underline{1}, \underline{2}, 2, 2, 2, 3]$$$;
- $$$f(1, 2) = 1$$$, because $$$[5, 4] \rightarrow [\underline{2}, \underline{3}, 4]$$$;
- $$$f(2, 3) = 1$$$, because $$$[4, 3] \rightarrow [\underline{1}, \underline{3}, 3]$$$;
- $$$f(1, 1) = f(2, 2) = f(3, 3) = 0$$$, because they are already non-decreasing.

So the total sum of extreme values of all subarrays of $$$a = 3 + 1 + 1 + 0 + 0 + 0 = 5$$$.

Example input:
4
3
5 4 3
4
3 2 1 4
1
69
8
7264 40515 28226 92776 35285 21709 75124 48163

Example output:
5
9
0
117

Editorial:
Let's find out how to calculate the extreme value of an array $$$a$$$ of $$$n$$$ integers. It turns out that a greedy solution exists!
Consider the rightmost index $$$i$$$ such that $$$a_i \gt a_{i + 1}$$$. So we must split $$$a_i$$$ into new (let's say $$$k$$$) elements $$$1 \le b_1 \le b_2 \le \ldots \le b_k \le a_{i+1}$$$ such that $$$b_1 + b_2 + \ldots + b_k = a_i$$$ . Notice that $$$k \ge \left\lceil \frac{a_i}{a_{i+1}} \right\rceil $$$ because $$$b_k \le a_{i+1}$$$. But it is always optimal to make $$$b_1$$$ as large as possible. It is not hard to see that the smaller the $$$k$$$, the bigger the $$$b_1$$$ we can achieve. So let's set $$$k = \left\lceil \frac{a_i}{a_{i+1}} \right\rceil$$$. Now, notice that $$$b_1 \le \left\lfloor \frac{a_i}{k} \right\rfloor$$$. So let's set $$$b_1 = \left\lfloor \frac{a_i}{k} \right\rfloor = \left\lfloor \frac{a_i}{\left\lceil \frac{a_i}{a_{i+1}} \right\rceil} \right\rfloor$$$. So we have performed $$$k - 1 = \left\lceil \frac{a_i}{a_{i+1}} \right\rceil - 1$$$ operations and will solve the problem analogously for the previous indices after replacing $$$a_i$$$ by $$$[b_1, b_2, \ldots, b_k]$$$.
To sum it all up, we can calculate the extreme value in the following procedure:
• Iterator from $$$i = n - 1$$$ to $$$1$$$.
• Add $$$\left\lceil \frac{a_i}{a_{i+1}} \right\rceil - 1$$$ to the answer.
• Set $$$a_i = \left\lfloor \frac{a_i}{\left\lceil \frac{a_i}{a_{i+1}} \right\rceil} \right\rfloor$$$.
Pretty elegant! Let's call it elegant procedure from now on.
So we can calculate the extreme value of an array of $$$n$$$ integers in $$$\mathcal{O}{(n)}$$$.
To solve it for all subarrays in $$$\mathcal{O}{(n^2)}$$$, we need to fix a prefix and solve each suffix of this prefix in a total of $$$\mathcal{O}{(n)}$$$ operations. We can do that easily because the procedure to calculate the extreme values starts from the end, so we can sum up the contributions on the run.
How to solve the problem faster?
Think dp.
Let $$$dp(i, x)$$$ be the count of subarrays $$$a[i;j]$$$ such that $$$i \le j$$$ and after the elegant procedure $$$x$$$ becomes the first element of the final version of that subarray.
We only care about the $$$x$$$s for which $$$dp(i, x)$$$ is non-zero. How many different $$$x$$$ is possible?
Well, it can be up to $$$10^5$$$, right?
Wrong!
Let's go back to our elegant procedure once again. For the time being, let's say for all $$$x = 1$$$ to $$$10^5$$$, $$$dp(i + 1, x)$$$ is non-zero. So for each $$$x$$$, we will add $$$dp(i + 1, x)$$$ to $$$dp(i, \left\lfloor \frac{a_i}{\left\lceil \frac{a_i}{x} \right\rceil} \right\rfloor)$$$.
But there can be at most $$$2 \sqrt{m}$$$ distinct values in the sequence $$$\left\lfloor \frac{m}{1} \right\rfloor, \left\lfloor \frac{m}{2} \right\rfloor, \ldots, \left\lfloor \frac{m}{m} \right\rfloor$$$. Check this for a proof.
So there can be $$$\mathcal{O}{(\sqrt{10^5})}$$$ distinct $$$x$$$s for which $$$dp(i, x)$$$ is non-zero. So we can solve this dp in $$$\mathcal{O}{(n \cdot \sqrt{10^5}})$$$. To optimize the space-complexity we can observe that we only need the dp values of $$$i + 1$$$. So we can use only two arrays to maintain everything. Check my solution for more clarity.
To get the final answer, we will use the contribution technique. To be precise, for each $$$(i + 1, x)$$$ we will add $$$i \cdot dp(i + 1, x) \cdot (\left\lceil \frac{a_i}{a_{i+1}} \right\rceil - 1)$$$ to our answer and its not hard to see this. Here, $$$i \cdot dp(i + 1, x)$$$ is the number of arrays where the $$$i$$$-th element will be set to $$$x$$$ in the elegant procedure and $$$\left\lceil \frac{a_i}{a_{i+1}} \right\rceil - 1$$$ is the number of operations that will be performed for the same.
Overall time complexity will be $$$\mathcal{O}{(n \cdot \sqrt{10^5}})$$$ and space complexity will be $$$\mathcal{O}(n)$$$.