Sorting a Sequence 4

Let $x_i$ be the number of times index $i$ is chosen. The total number of operations is subtracted from every element, so it does not affect sortedness. We require $A_i+2x_i\leq A_{i+1}+2x_{i+1}$. Start with $x_1=0$ and choose $x_i=\max(0,x_{i-1}+\lceil(A_{i-1}-A_i)/2\rceil)$. Increasing an earlier choice cannot lower any later bound, so this greedy choice is optimal.

Each $x_i$ is at most $5\cdot10^8+50000$, so the total number of operations is at most $5.0005\cdot10^{13}$. Thus the exact answer fits in a signed 64-bit integer. Handle ceiling division for negative differences correctly. The time complexity is .

Solution written by GPT6