Codeforces Round 154 (Div. 2) |
---|
Закончено |
На физическом практикуме Вася делал задание по измерению емкости конденсатора. По рекомендации преподавателя, он сделал не одно, а целых n измерений, и записал их результаты в тетрадку. После этого он уже собирался показывать результаты преподавателю, но вспомнил, что на прошлом занятии учитель заставил его друга Петю переделывать эксперимент из-за того, что наибольший и наименьший результаты измерений отличались более чем в два раза. Вася — ленивый, и он не хочет ничего переделывать. Он хочет сдать задание и пойти домой играть в компьютерные игры. Поэтому он решил пойти на хитрость: прежде, чем показывать результаты измерений преподавателю, он сотрет какие-то из них, причем сотрет так, чтобы наибольший и наименьший результаты оставшихся измерений отличались не более, чем в два раза. Другими словами, если среди оставшихся измерений наименьший результат измерения x, а наибольший результат — y, то должно выполняться неравенство y ≤ 2·x. Разумеется, чтобы не вызвать подозрений преподавателя, Вася хочет стереть как можно меньше результатов изменений из своих записей.
Помогите Васе, найдите какое наименьшее количество результатов измерений ему придется стереть из своих записей, чтобы наибольший и наименьший результаты оставшихся измерений отличались не более, чем в два раза.
В первой строке записано целое число n (2 ≤ n ≤ 105) — количество проведенных измерений. Во второй строке записано n целых чисел c1, c2, ..., cn (1 ≤ ci ≤ 5000) — результаты измерений. Числа во второй строке разделяются одиночными пробелами.
Выведите единственное целое число — наименьшее количество результатов, которое Васе придется стереть.
6
4 5 3 8 3 7
2
4
4 3 2 4
0
В первом примере можно удалить четвертый и шестой результаты измерений (значения 8 и 7). Тогда наибольшим из оставшихся значений будет 5, а наименьшим — 3. Или же можно удалить третий и пятый результаты (оба равны 3). При таком способе наибольшим из оставшихся значений будет 8, а наименьшим — 4.
Название |
---|