P2501 [HAOI2006] Number Sequence

You are given an integer sequence $a$ of length $n$. It does not look good, so we want to turn it into a strictly increasing sequence. However, we do not want to change too many elements, and we also do not want the magnitude of changes to be too large.

The first line contains an integer $n$, the length of the sequence. The second line contains $n$ integers; the $i$-th integer is the $i$-th element $a_i$ of the sequence.

On the first line, output an integer: the minimum number of elements that need to be changed. On the second line, output an integer: under the condition that the number of changed elements is minimal, the minimum possible sum of absolute changes.

Constraints - For $90\%$ of the testdata, it is guaranteed that $n \leq 6 \times 10^3$. - For $100\%$ of the testdata, it is guaranteed that $1 \leq n \leq 3.5 \times 10^4$, $1 \leq a_i \leq 10^5$. The testdata guarantees that $a_i$ are generated at random. Translated by ChatGPT 5