Let’s set $$$k = 1$$$ just for now to make everything more simple. We know that the answer for $$$k = 1$$$ is given by the expression $$$a_1 + max(a_2 - a_1, 0) + max(a_3 - a_2, 0) … + max(a_n - a_{n-1}, 0).$$$ The editorial does a good job in explaining this in my opinion. Instead of writing the answer in this form, though, what if we tried to make each $$$a_i$$$ independent of one another? In other words, we want to express the answer as $$$c_1 \cdot a_1 + c_2 \cdot a_2 + … + c_n \cdot a_n$$$ where each $$$c_i$$$ is some coefficient. Let’s see how we can do this:

Let’s solve it for an array of length $$$2.$$$

The current expression is $$$a_1 + max(a_2 - a_1, 0).$$$

Let’s define an array coefficients = $$$[0, 0]$$$ where $$$coefficients_i =$$$ the coefficient of $$$a_i.$$$

We know that we have $$$a_1$$$ isolated in the current expression. So we can set $$$coefficients_1 = 1.$$$

But how do we deal with the $$$max(a_2 - a_1, 0)$$$ case?

Let’s assume that $$$a_2 - a_1 > 0.$$$ Well then the $$$max(a_2 - a_1, 0) = a_2 - a_1.$$$ So the expression becomes $$$a_1 + a_2 - a_1.$$$ It can be seen that when $$$a_2 - a_1 > 0,$$$ we add one to $$$coefficients_2$$$ and we subtract one from $$$coefficients_1.$$$ Our coefficients array will then be $$$[0, 1],$$$ and our answer will be $$$c_1 * a_1 + c_2 * a_2,$$$ or just $$$a_2.$$$

What happens when $$$a_2 - a_1 < 0$$$? Well then $$$max(a_2 - a_1, 0) = 0$$$ and our expression will just be $$$a_1 + 0.$$$ Notice that this does not change our original coefficients array at all so we don’t actually have to change any coefficients. The answer is just $$$a_1.$$$

What about when $$$a_2 - a_1 == 0$$$? Well in this case, we can either not change our coefficients or add one to $$$coefficients_2$$$ and subtract one from $$$coefficients_1.$$$ Since $$$a_2 == a_1,$$$ these operations are equivalent.

We can do this for all of the $$$max(a_{i + 1} - a_i, 0)$$$ values, adding and subtracting from coefficients when necessary.

Code might look something like this:

coefficients = [0] * (len(arr) + 10)
coefficients[0] = 1
 
for i in range(len(arr) - 1):
	if arr[i + 1] > arr[i]:
		coefficients[i + 1] += 1
		coefficients[i] -= 1

And we have solved the problem independently for each $$$a_i$$$ when $$$k = 1.$$$

What about when $$$k \ne 1$$$? Does it affect our coefficients? $$$k$$$ changes our $$$a_i$$$ to $$$\lceil \frac{a_i}{k} \rceil$$$ so it must affect $$$max(a_{i + 1} - a_i, 0)$$$ and thus coefficients, right?

No. There are two cases

Case 1: changing all $$$a_i$$$ to $$$\lceil \frac{a_i}{k} \rceil$$$ does not change the relative size of all $$$a_i.$$$ In other words, for all $$$i < n,$$$ if $$$a_{i + 1} > a_i,$$$ then $$$\lceil \frac{a_{i + 1}}{k} \rceil > \lceil \frac{a_i}{k} \rceil,$$$ and if $$$a_{i + 1} < a_i,$$$ then $$$\lceil \frac{a_{i + 1}}{k} \rceil < \lceil \frac{a_i}{k} \rceil.$$$ This doesn’t affect the answer because the coefficients are made based on the relative size of each $$$a_i,$$$ not the absolute size. Like if $$$a_{i + 1} > a_i,$$$ then we are adding $$$1$$$ to $$$c_{i + 1}$$$ and subtracting $$$1$$$ from $$$c_i$$$ no matter the size of $$$a_{i + 1}$$$ and $$$a_i.$$$

Case 2: Changing all $$$a_i$$$ to $$$\lceil \frac{a_i}{k} \rceil$$$ changes the relative size of some $$$a_i.$$$ In other words, for some $$$i,$$$ if $$$a_{i + 1} > a_i,$$$ then $$$\lceil \frac{a_{i + 1}}{k} \rceil = \lceil \frac{a_i}{k} \rceil$$$ or if $$$a_{i + 1} < a_i$$$ then $$$\lceil \frac{a_{i + 1}}{k} \rceil = \lceil \frac{a_i}{k} \rceil$$$ (notice that if $$$a_{i + 1} > a_i,$$$ we can never have $$$\lceil \frac{a_{i + 1}}{k} \rceil < \lceil \frac{a_i}{k} \rceil.$$$ But we see that, in either of these cases, when we originally processed the $$$max(a_{i + 1} - a_i, 0), coefficients_{i + 1}$$$ got the same number of $$$1$$$ additions as $$$coefficients_i$$$ got $$$1$$$ subtractions (that is, either $$$coefficients_{i + 1} += 1$$$ and $$$coefficients_i -= 1,$$$ or they remained unchanged). Since $$$\lceil \frac{a_{i + 1}}{k} \rceil = \lceil \frac{a_i}{k} \rceil,$$$ the coefficients do not matter since they “balance” each other out.

So coefficients doesn’t just work for $$$k = 1,$$$ it works for all $$$k.$$$

The editorial makes it clear why there are only up to $$$2\sqrt{a_i}$$$ possible $$$\lceil \frac{a_i}{k} \rceil$$$ values for every $$$a_i.$$$ So, using this fact, for each $$$a_i,$$$ we can find the ranges of $$$k$$$ that make $$$\lceil \frac{a_i}{k} \rceil$$$ equal to the same value. For a specific value $$$x,$$$ say $$$L$$$ is the lower bound of the $$$k$$$ range and $$$R$$$ is one above the upper bound. We can just use a difference array called $$$ans$$$ and do $$$ans_L += c_i \cdot x$$$ and $$$ans_R -= c_i \cdot x.$$$ Let’s say we start at $$$k = 1$$$ and this will be our first $$$L$$$ for some $$$x.$$$ How can we efficiently find $$$R$$$?

We know that:

$$$\lceil \frac{a_i}{L} \rceil = x.$$$

Since $$$R > L,$$$ we know that $$$\lceil \frac{a_i}{R} \rceil < x.$$$

$$$\lceil \frac{a_i}{R} \rceil \le x - 1$$$

So $$$\frac{a_i}{R} \le x - 1$$$

$$$\frac{a_i}{x - 1} \le R$$$

$$$R = \lceil \frac{a_i}{x - 1} \rceil$$$

We can set $$$L = R$$$ and then do the same steps for the new $$$L$$$ until we have covered all of the ranges. This solution is too slow for python so I had to convert it to c++

from math import ceil
import random
 
def thing(arr):
	if len(arr) == 1:
		ans = []
		for i in range(1, arr[0] + 1):
			ans.append(ceil(arr[0] / i))
		print(*ans)
		return
 
	max_arr = max(arr)
	coefficients = [0] * (len(arr) + 10)
	coefficients[0] = 1
	ans = [0] * (max(arr) + 100)
	ans2 = []
 
	for i in range(len(arr) - 1):
		cur = 0
		if arr[i + 1] > arr[i]:
			coefficients[i + 1] += 1
			coefficients[i] -= 1
 
 
	for i, val in enumerate(arr):
		k = 1
 
		while True:
			x = ceil(val / k)
			if x == 1:
				ans[k] += coefficients[i]
				break
			ans[k] += coefficients[i] * x
			new_k = ceil(val / ceil(x - 1))
			if new_k < len(ans):
				ans[new_k] -= x * coefficients[i]
			k = new_k
 
	pre = 0
	for i in range(1, max(arr) + 1):
		pre += ans[i]
		ans2.append(pre)
 
 
	print(*ans2)
 
input()
thing([int(i) for i in input().split()])

I believe that the editorial does a good job in explaining this one. Here is my implementation anyway (I finally got AC with python).

from math import ceil
 
def thing(arr):
	if len(arr) == 1:
		ans = []
		for i in range(1, arr[0] + 1):
			ans.append(ceil(arr[0] / i))
		print(*ans)
		return
 
	max_arr = max(arr)
	coefficients = [0] * (max_arr + 10)
	ans = [0] * (max_arr + 1)
	
	coefficients[arr[0]] = 1
 
	for i in range(len(arr) - 1):
		if arr[i + 1] > arr[i]:
			coefficients[arr[i + 1]] += 1
			coefficients[arr[i]] -= 1
 
 
	pre2 = []
	pre = 0
 
	for i in coefficients:
		pre += i
		pre2.append(pre)
 
	for k in range(1, max_arr + 1):
		for x in range(1, max_arr // k + 2):
			ans[k] += x * (pre2[min(k * x, max_arr)] - pre2[k * (x - 1)])
 
	print(*ans[1:])
 
input()
thing([int(i) for i in input().split()])