P10989 [Lanqiao Cup 2023 National Python A/Java A] Isosceles Triangle

Python users are recommended to submit this problem using PyPy3.

Given a sequence $A_i$ containing $n$ numbers, in each operation you may choose any number and change it by $+1$ or $-1$. We want to make this sequence satisfy the following condition: no matter which three numbers you choose from it, the three corresponding lengths can always form an isosceles triangle. Find the minimum number of operations needed to make the sequence satisfy this condition.

The first line contains an integer $n$. The second line contains $n$ integers, representing $A_1, A_2, \cdots, A_n$, separated by a single space.

Output one line containing an integer, representing the minimum number of operations.

For $40\%$ of the test cases, $n \le 5000, A_i \le 5000$. For $70\%$ of the test cases, $n \le 2 \times 10^5, A_i \le 10^6$. For all test cases, $1 \le n \le 2 \times 10^5, 1 \le A_i \le 10^9$. #### Sample Explanation You can modify the original sequence to $4, 4, 4, 7, 7$. Translated by ChatGPT 5