Background

Python users are recommended to submit this problem using PyPy3.

Problem Description

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.

Input Format

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 Format

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

5
3 3 5 7 7

3

Hint

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