Назар отримав завдання, яке скдадається із N задач. Кожна із задач оцінюється балами від 0 до 10000. Професор планує поставити заліковий бал за алгоритмом: відкидається задача, по якій студент набрав найменше балів, і знаходиться середнє арифметичне від залишку балів.
Професор під час заліку дозволив Назару відкинути бали \(K\) (\(1 \le K \le N-2\)) перших задач перед оцінюванням. Яку кількість задач має відкинути Назар, щоб отримати максимальну оцінку за алгоритмом професора?
Формат вхідних даних
Єдиний рядок вхідного потоку містить ціле число \(N\) (\(3 \le N \le 100000\)) - кількість задач.
Формат вихідних даних
Вивести по одному у рядку всі можливі значення \(K\) у зростаючому порядку, при яких Назар отримає максимальну оцінку.
Примітка
До прикладу 1:
Якщо відкинути перші 2 оцінки, то залишиться 9,2,7. Відкинемо 2 і отримаємо середню оцінку 8 балів. Це є максимальна оцінка.
Приклад вхідних даних
5
3 1 9 2 7
Приклад вихідних даних
2
Коментарі
що ж там за числа такі після третього кейсу, що часу не вистачає, перевіряв у себе на 1000 чисел(числа від 1 до 1000), мій код затрачає менше половини секунди. А тут двох не вистачає... здається що мій алгоритм має важкість o(k*n) 1<=k<=10.
Перевірте, будь ласка, останній тест. Мені здається, там щось не те
"Вивести по одному у рядку всі можливі значення 𝐾..." - все решту ok ;)
Зрозумів, дякую
А, там є написано... Я не помітив)
Які обмеження на кількості балів?