У вас есть \(n\) палочек с положительными целочисленными длинами \(a_1, a_2, \ldots, a_n\).
Вы можете выполнить следующую операцию произвольное число раз (возможно, ноль):
- выберите одну палочку, затем увеличьте или уменьшите ее длину на \(1\). После каждой операции длины всех палочек должны остаться положительными.
Какое минимальное число операций необходимо, чтобы вы могли выбрать три палочки из данных \(n\) и сложить их, не ломая, в равносторонний треугольник?
Равносторонним треугольником называется треугольник, у которого все три стороны равны.
Выходные данные
Для каждого набора входных данных выведите одно целое число — минимально необходимое число операций.
Примечание
В первом примере можно увеличить длину первой палочки на \(1\), затем уменьшить длину третьей палочки на \(1\). Всего вы сделаете \(2\) операции, и сможете взять три палочки, чтобы собрать равносторонний треугольник с длиной стороны \(2\).
In the fourth test case, you can decrease the length of the seventh stick by \(1\). An equilateral triangle of side length \(1\) can be selected and formed by the second, fourth, and seventh sticks.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
3
1 2 3
4
7 3 7 3
5
3 4 2 1 1
8
3 1 4 1 5 9 2 6
|
2
4
1
1
|