У них багато маленьких хлопчиків і дівчаток у Китаї. Ще трохи хлопчиків. І навіть більше рису.
Однак останнім часом у їхніх садочках стає все більше плачучих і нещасних дітей. Вони почали вивчати математику. Зокрема, до цього часу вони навчилися рахувати великі числа, а також множити і ділити на два.
Ви можете подумати, що у них багато домашніх завдань або що вони не люблять математику. Однак все навпаки. Отримавши цю нову наддержаву, вони використовують її щодня. Особливо в обід. Перш ніж почати їсти, кожен підраховує свої рисові зерна. 1
Коли кожен порахував свій рис, починається друга фаза обіду. Порівняння. Якщо хтось дізнається, що у нього вдвічі більше зерен, ніж у однокласника, він має право на підвищення та висміювання. Потім плаче слідом, або поранений хлопчик чи дівчинка знаходить когось, у кого вдвічі більше рису. Діти часом бувають жорстокими.
Вихователі безглузді. Вони ніколи не переживали стільки плачу та творчої лайки, як чули за останній період. Звичайно, процес навчання швидко зупинився, але дітей не можна навчити з того, що вони вже знають.
Тому, як альтернативу, вони хотіли б взяти деяким дітям рис і дати їм тофу. Рис слід брати у дітей, щоб у двох розплідниках \ (x \) та \ (2x \) не було рисових зерен. Педагоги розуміють, що тофу 2 ніхто не любить, тому вони хотіли б його дарувати якомога менше діти. Їх також цікавило б, скільки дітей може взяти найменшу кількість рисових тарілок і роздати тофу.
Завдання
\ (N \) порції рису готуються до обіду. Ви дізнаєтесь одне число про кожну порцію - кількість рисових зерен. Ці числа розташовані у порядку зростання на вході. Вам потрібно взяти кілька порцій, щоб ніхто не отримав удвічі більше рису, ніж хтось інший. Іншими словами, не повинно залишитися двох частин, на яких є зерна \ (x \) та \ (2x \). Ви намагаєтеся видалити якомога менше частин.
Також з’ясуйте, скільки порцій можна вилучити, щоб задовольнити попередні вимоги. Два шляхи різні, якщо є хоча б одна частина, яка залишилася в нас одним способом, а не в іншому. Оскільки цих методів може бути дуже багато, запишіть лише залишок після ділення на просте число \ (1 \, 000 \, 000 \, 009 \) .
Формат введення
У першому рядку введення є додатне ціле число \ (n \), що не перевищує \ (1 \, 000 \, 000 \), що вказує на кількість порцій. Наступний рядок супроводжується \ (n \) числами \ (r_i \), розділеними пробілами, причому \ (0 для кожного з них. Числа \ (r_i \) розташовані від найменшого до найбільшого.
Вихідний формат
Напишіть два цілі числа, розділені пробілом: найбільшу можливу кількість частин, які залишаться перемодульованими \ (1 \, 000 \, 000 \, 009 \) після видалення необхідних пластин та кількості способів їх вибору. Завершіть вихід символом нового рядка.
Приклад
Вхідні дані:
Вихід:
Жодної акції та якомога менше тофу, залишаючи дітям такі порції: 1 3 4 5 5, 1 4 5 5 6, 2 2 3 5 5, 2 2 5 5 6
Завдяки цій забаві вони також обідають кілька годин, тому їм не потрібно лягати спати вдень
І весь той рис хтось теж повинен з’їсти
Завантаження
Для завантаження потрібно ввійти в систему
Запитання та обговорення
Наприкінці раунду у вас буде можливість обговорити рішення в дискусії під типовим рішенням.