Дан массив \(a\) из \(n\) элементов \(a_1, a_2, \ldots, a_n\).
Вы можете выполнить следующую операцию любое количество раз (возможно, \(0\)):
- Выберите два целых числа \(i\) и \(j\), где \(1 \le i, j \le n\), и присвойте \(a_i := a_j\).
Найдите минимальное количество операций, необходимых для того, чтобы массив \(a\) удовлетворял условию:
- Для каждой попарно различной тройки индексов \((x, y, z)\) (\(1 \le x, y, z \le n\), \(x \ne y\), \(y \ne z\), \(x \ne z\)) существует невырожденный треугольник со сторонами длиной \(a_x\), \(a_y\) и \(a_z\), т.е. \(a_x + a_y > a_z\), \(a_y + a_z > a_x\) и \(a_z + a_x > a_y\).
Выходные данные
Для каждого набора входных данных выведите одно целое число — минимальное количество операций, необходимых для достижения цели.
Примечание
В первом наборе входных данных одна из возможных последовательностей операций может быть следующей:
- Присвоить \(a_1 := a_4 = 4\). Массив станет \([4, 2, 3, 4, 5, 6, 7]\).
- Присвоить \(a_2 := a_5 = 5\). Массив станет \([4, 5, 3, 4, 5, 6, 7]\).
- Присвоить \(a_7 := a_1 = 4\). Массив станет \([4, 5, 3, 4, 5, 6, 4]\).
Можно доказать, что любая тройка элементов с попарно различными индексами в итоговом массиве образует невырожденный треугольник, и нет возможного ответа с использованием менее чем \(3\) операций.
Во втором наборе входных данных мы можем присвоить \(a_1 := a_2 = 3\), чтобы получить массив \(a = [3, 3, 2]\).
В третьем наборе входных данных, поскольку \(3\), \(4\) и \(5\) являются допустимыми длинами сторон треугольника, нам не нужно выполнять никаких операций с массивом.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
7
1 2 3 4 5 6 7
3
1 3 2
3
4 5 3
15
9 3 8 1 6 5 3 8 2 1 4 2 9 4 7
|
3
1
0
8
|