Назовем массив из \(k\) целых чисел \(c_1, c_2, \ldots, c_k\) ужасным, если выполняется следующее условие:
Пусть \(AVG\) — это \(\frac{c_1 + c_2 + \ldots + c_k}{k}\) (то есть среднее значение всех элементов массива, не обязательно целое). Тогда количество элементов массива, которые больше \(AVG\), должно быть строго больше количества элементов массива, которые меньше \(AVG\). Обратите внимание, что элементы, равные \(AVG\), не учитываются.
Например, \(c = \{1, 4, 4, 5, 6\}\) является ужасным, потому что \(AVG = 4.0\) и \(5\)-й и \(4\)-й элементы больше \(AVG\), а \(1\)-й элемент меньше \(AVG\).
Назовем массив из \(m\) целых чисел \(b_1, b_2, \ldots, b_m\) плохим, если хотя бы одна из его непустых подпоследовательностей ужасна, и хорошим в противном случае.
Вам дан массив из \(n\) целых чисел \(a_1, a_2, \ldots, a_n\). Найдите минимальное количество элементов, которые нужно удалить из него, чтобы получить хороший массив.
Массив является подпоследовательностью другого массива, если он может быть получен из него путем удаления нескольких (возможно, нуля или всех) элементов.
Выходные данные
Для каждого набора входных данных выведите минимальное количество элементов, которые нужно удалить из него, чтобы получить хороший массив.
Примечание
В первом примере массив \(a\) уже хороший.
Во втором примере достаточно удалить \(1\), получив массив \([4, 4, 5, 6]\), который является хорошим.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
3
1 2 3
5
1 4 4 5 6
6
7 8 197860736 212611869 360417095 837913434
8
6 10 56026534 405137099 550504063 784959015 802926648 967281024
|
0
1
2
3
|