Minimum Operations to Form Universally Isosceles Triangle Sequence

Given a sequence of n numbers \(A_i\), you can perform an operation that increments or decrements any chosen number by 1. The goal is to modify the sequence with the minimum total number of operations so that any three numbers chosen (in any order) can serve as the side lengths of an isosceles triangle (a triangle with at least two equal sides). In other words, the final sequence should have at most two distinct numbers. Moreover, if the final sequence contains two distinct numbers \(x\) and \(y\) (assume \(x<y\)), then they must satisfy the triangle inequality for the isosceles triangle formed by \(x,x,y\), i.e.,

[ 2x > y ]

This ensures that the triangle with sides \(x, x, y\) is valid since \(x+x>y\) and obviously the other two inequalities hold when \(x, y > 0\).

Determine the minimum number of operations required to achieve such a configuration.

inputFormat

The first line contains an integer \(n\) (the number of elements in the sequence).
The second line contains \(n\) space-separated integers \(A_1, A_2, \dots, A_n\).

outputFormat

Output a single integer: the minimum number of operations required to transform the sequence so that any three numbers can form an isosceles triangle as described above.

sample

3
1 2 3

1