Рассмотрим неубывающую последовательность s
1, ..., s
n + 1 ( s
i <= s
i + 1 для 1 <= i <= n ). Последовательность m
1, ..., m
n, в которой каждый член определен как m
i = ½ * ( s
i + s
i + 1 ) для 1 <= i <= n, назовем “средней последовательностью” для последовательности s
1, ... s
n + 1. Например, средняя последовательность для последовательности 1, 2, 2, 4 есть 1.5, 2, 3. Заметим, что элементы средней последовательности могут быть дробными числами. Тем не менее, в данной задаче используются только те средние последовательности, в которых все числа целые. Для заданной неубывающей последовательности из n целых чисел m1, ..., mn необходимо вычислить количество всех неубывающих последовательностей из n + 1 целых чисел s
1, ..., s
n + 1, для которых заданная последовательность m
1, ..., m
n является средней последовательностью.
Задание
Напишите программу, которая:
• читает из стандартного ввода неубывающую последовательность целых чисел;
• вычисляет количество всех неубывающих последовательностей целых чисел, для которых заданная последовательность является средней последовательностью;
• выводит ответ в стандартный вывод.
Входные данные
Первая строка стандартного ввода содержит одно целое число n (2 <= n <= 5000000). Оставшиеся n строк содержат значения последовательности m
1, ..., m
n. Строка i + 1 содержит одно целое число mi (0 <= mi <= 1000000000).
Выходные данные
Ваша программа должна вывести в стандартный вывод ровно одно целое число – количество всех неубывающих последовательностей целых чисел, для которых входная последовательность является средней последовательностью.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
2
5
9
|
4
|