У Eshag есть массив \(a\), состоящий из \(n\) целых чисел.
Eshag может выполнить следующую операцию любое количество раз: выбрать некоторую подпоследовательность \(a\) и удалить из нее каждый элемент, который строго больше чем \(AVG\), где \(AVG\) — среднее арифметическое значение чисел в выбранной подпоследовательности.
Например, если \(a = [1 , 4 , 3 , 2 , 4]\) и Eshag применит операцию к подпоследовательности, содержащей \(a_1\), \(a_2\), \(a_4\) и \(a_5\), то он удалит те из этих \(4\) элементов, которые больше чем \(\frac{a_1+a_2+a_4+a_5}{4} = \frac{11}{4}\), поэтому после операции массив \(a\) станет \(a = [1 , 3 , 2]\).
Ваша задача — найти максимальное количество элементов, которые Eshag может удалить из массива \(a\), применив описанную выше операцию несколько (возможно, ноль) раз.
Последовательность \(b\) является подпоследовательностью массива \(c\), если \(b\) может быть получена из \(c\) путем удаления нескольких (возможно, нуля или всех) элементов.
Выходные данные
Для каждого наборов входных данных выведите одно целое число — максимальное количество элементов, которые Eshag может удалить из массива \(a\).
Примечание
Рассмотрим первый набор входных данных.
Первоначально \(a = [1, 1, 1, 2, 2, 3]\).
В первой операции Eshag может выбрать подпоследовательность, содержащую \(a_1\), \(a_5\) и \(a_6\), их среднее арифметическое равно \(\frac{a_1 + a_5 + a_6}{3} = \frac{6}{3} = 2\). Поэтому \(a_6\) будет удалено.
После этого \(a = [1, 1, 1, 2, 2]\).
Во второй операции Eshag может выбрать подпоследовательность, содержащую весь массив \(a\), среднее арифметическое всех его элементов равно \(\frac{7}{5}\). Поэтому \(a_4\) и \(a_5\) будут удалены.
После этого \(a = [1, 1, 1]\).
Во втором наборе входных данных Eshag не может удалить ни одного элемента.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
6
1 1 1 2 2 3
6
9 9 9 9 9 9
6
6 4 1 1 4 1
|
3
0
3
|