В Китай имат много малки момчета и момичета. Още малко момчета. И още повече ориз.
Напоследък обаче в техните детски градини има все повече плачещи и нещастни деца. Започнаха да учат математика. По-специално, досега те са се научили да броят на големи числа, а също и да умножават и делят по две.
Може би си мислите, че имат много домашни или че не обичат математиката. Вярно е обаче обратното. След като придобият тази нова суперсила, те я използват всеки ден. Особено на обяд. Преди да започнат да ядат, всеки си брои оризовите зърна. 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
Благодарение на това забавление те също обядват за няколко часа, така че не е нужно да си лягат следобед
И целият този ориз също трябва да бъде изяден от някого
Качване
Трябва да сте влезли, за да качите
Въпроси и дискусия
В края на кръга ще имате възможност да обсъдите решения в дискусия под моделно решение.