Hints: Sum of Fractions

For a single subarray $b$ and one fraction $\frac{1}{b_i}$, what happens if you use all $k$ increases on that fraction? You can either add 1 to the numerator $k$ times, or decrease the denominator, or mix. To maximize the value of that fraction, is it better to decrease the denominator or increase the numerator?

Answer to Hint 1: Decreasing the denominator increases the fraction more (e.g. $\frac{1}{d} \to \frac{1}{d-1}$ is a bigger gain than $\frac{1}{d} \to \frac{2}{d}$ when $d$ is small). So to maximize the sum of fractions, you typically want to apply as many “denominator decrease” operations as possible to the fraction(s) with the smallest denominator, then possibly add numerator increases.

For $\mathrm{MSF}(b, k)$, a natural strategy is: always choose the fraction with the smallest current denominator to increase (and prefer decreasing its denominator if $y > 1$). This greedy can be analyzed to get a closed form.

Answer to Hint 2: For a fixed subarray, the optimal strategy leads to a formula for $\mathrm{MSF}(a[l..r], k)$ that depends on the minimum value in the subarray and the sum of $\frac{1}{a_i}$ over the subarray, plus corrections that depend on $k$ and which element is minimum.

So the answer for a given $k$ is $\sum_{l,r} \mathrm{MSF}(a[l..r], k)$. You need to sum over all subarrays. How can you avoid iterating over all $O(n^2)$ subarrays?

Answer to Hint 3: Use the fact that each position $p$ is the minimum of some subarrays. For a fixed $p$, the subarrays whose minimum is at $p$ are those $[l, r]$ with $l \le p \le r$ and $a[p] = \min a[l..r]$. The number of such pairs $(l,r)$ can be computed with a range-min structure (e.g. segment tree or sparse table) and standard “count subarrays where this is min” trick: for each $p$, find left and right boundaries where $a[p]$ is strictly the minimum, then the count is $(p - l + 1)(r - p + 1)$.

Answer to Hint 4: So you can do a divide-and-conquer by minimum (or use a stack to compute left/right “next smaller” for each index). For each index $p$, compute $\mathrm{mul}[p] = (p - l + 1)(r - p + 1)$ in the appropriate sense. Then the contribution of a subarray with minimum at $p$ to $\mathrm{MSF}(\cdot, k)$ can be expressed in terms of $a[p]$, $k$, and possibly prefix sums of $1/a_i$ over the subarray.

Answer to Hint 5: The exact formula for the contribution involves: the base sum (sum of $1/a_i$ over the subarray) plus an extra from the $k$ increases. When the minimum is at $p$, the extra often takes the form of a linear function in $k$ (or in $\min(k, a_p - 1)$ etc.), multiplied by how many subarrays have that minimum. So you get terms like $\mathrm{mul}[p] \cdot f(a_p, k)$ for some $f$.

Answer to Hint 6: To handle multiple $k$ values efficiently, observe that $k_i$ are given in non-decreasing order. The closed form for each index $p$ is a function of $k$ that is piecewise (e.g. constant for $k \le$ something, then linear in $k$). You can sort elements by $a_i$, build prefix sums of $\mathrm{mul}[p] \cdot (\ldots)$ and $\mathrm{mul}[p] \cdot a_p$, etc., so that for each query $k$ you do a binary search and combine these prefix sums to get the total answer in $O(\log n)$ per query.

Answer to Hint 7: Implementation sketch: (1) Build range-min structure (sparse table or segment tree). (2) For each $p$, compute left/right extent where $a[p]$ is minimum; set $\mathrm{mul}[p] = (p - l + 1)(r - p + 1)$. (3) Precompute prefix sums of $1/a_i$ and $i \cdot (1/a_i)$ for the base sum over subarrays. (4) Express the “delta” from $k$ increases as a function of $k$ and $a_p$; sort by $a_p$ and build arrays $f$, $g_1$, $g_2$ so that for query $k$ you can compute $\mathrm{base} + f[\ldots] \cdot (k+1) + g_2[\ldots] \cdot (k+2) - g_1[\ldots]$ in modular arithmetic.

Answer to Hint 8: All arithmetic is modulo $998244353$. You need modular inverse for each $a_i$ (e.g. $\mathrm{inv}[i] = a_i^{-1} \bmod P$). The base contribution from subarrays can be accumulated in the divide-and-conquer by minimum: when you have segment $[l, r]$ with minimum at $p$, the sum of “base fraction sums” over subarrays with min at $p$ can be written using prefix sums of $\mathrm{inv}$ and $\mathrm{inv} \cdot \mathrm{index}$.

Answer to Hint 9: For each query $k_i$, the answer is $\mathrm{base}$ plus a term that depends on which elements have $a_p \le k_i + 2$ (or similar threshold). Use binary search to find the split, then add the precomputed prefix contributions. Output each result as an integer in $[0, 998244353)$.