Вниз по піраміді#11628
Вам подобаються числові піраміди? Зазвичай, для числової послідовності, яка є основою, потрібно побудувати решту "піраміди" знизу вгору: для кожної пари сусідніх чисел обчислюється їхня сума і записується над ними. Наприклад, для базової послідовності [1, 2, 3] послідовність безпосередньо над нею буде , а вершина піраміди буде :
Однак мене не цікавить завершення піраміди — натомість я хочу заглибитися під землю. Таким чином, для послідовності з невід'ємних цілих чисел я запишу під нею послідовність з n + 1 невід'ємних цілих чисел таку, що кожне число в початковій послідовності є сумою двох чисел, які я поставив під нею. Проте може існувати кілька можливих послідовностей, а можливо, і жодної, що задовольняє цій умові. Отже, чи можете ви визначити, зі скількох послідовностей я зможу вибрати?
У першому рядку записана довжина n (1 \le n \le 10^6) базової послідовності.
Наступний рядок містить цілих чисел a_1, ..., a_n~(0 \le a_i \le 10^8 для кожного ) — базову послідовність.
Виведіть кількість невід'ємних цілочислових послідовностей, для яких вхідна послідовність буде наступним рівнем у числовій піраміді.
Приклад 1
Приклад 2