The time when the balls are completely sorted is when all balls are in a state (let’s call it state A) where “all lighter balls are below themselves.” Therefore, we find the time when each ball reaches this state, and the maximum of these times is the answer.

We don’t need to consider balls of weight \(0\), so we’ll focus on the balls with positive weights. By observing the movement of the balls, we can see the following:

• From a certain time, the balls move along a line where \(t - j\) is constant (where \(j\) is the cell number), entering from the upper half region (\(1 \leq j \leq N\)) into the lower half region (\(N+1 \leq j \leq 2N\)), and continue increasing \(j\) until reaching state A.

We determine the value of \(t - j\) above for each ball.

First, the heaviest ball can adopt its initial value of \(t - j\). Here, the range of \(\pm 1\) around this value is occupied by the lighter balls that will rise when this ball moves down, so it’s determined that the values within the range of \(\pm 1\) cannot be adopted afterward. The next heaviest ball adopts its initial value if it does not fall within this range; otherwise, it takes the smallest possible value greater than that range. Since the movements of the lighter balls are not yet fixed, it’s guaranteed that these movements are possible. By repeating this process, we can determine the value of \(t - j\) for all balls.

Next, we find the time when each ball reaches state A. To do this, for each ball, we need to find the number of heavier balls below it when it moves along the trajectory where \(t - j\) is constant.

By the way, from the way \(t - j\) is determined, we can see that the maximum value of \(t - j\) is at least \(N - 2\). Therefore, even if the ball assigned to this \(t - j\) is the lightest among the positive weight balls and reaches state A at \(j = N + 1\), the time will be at least \(2N - 1\). In the negative range of \(t - j\), even if the ball doesn’t reach state A until \(j = 2N\), the time will be at most \(2N - 1\), so it’s sufficient to find the times for balls assigned to non-negative \(t - j\).

Furthermore, in the region where \(t - j \geq 0\), we see that \(t - j\) are simply arranged in descending order of ball weights. Therefore, in this region, all heavier balls have already sunk before, and we can see that the ball reaches state A at \(j = N + w\) (where \(w\) is its weight).

Incidentally, skipping the latter part of the consideration, we can also use a segment tree or similar data structure to find, for all balls, the number of heavier balls on trajectories with smaller \(t - j\).

From the above, we can obtain the answer.

Sample implementation: https://atcoder.jp/contests/arc188/submissions/60033454