Задача №567. Средняя последовательность
Рассмотрим неубывающую последовательность \(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\) целых чисел \(m_1\), ..., \(m_n\) необходимо вычислить количество всех неубывающих последовательностей из \(n\) + 1 целых чисел \(s_1\), ..., \(s_n\) + 1, для которых заданная последовательность \(m_1\), ..., \(m_n\) является средней последовательностью.
Напишите программу, которая:
• читает из стандартного ввода неубывающую последовательность целых чисел;
• вычисляет количество всех неубывающих последовательностей целых чисел, для которых заданная последовательность является средней последовательностью;
• выводит ответ в стандартный вывод.
Первая строка стандартного ввода содержит одно целое число \(n\) (2 <= \(n\) <= 5000000). Оставшиеся n строк содержат значения последовательности \(m_1\), ..., \(m_n\). Строка \(i\) + 1 содержит одно целое число \(m_i\) (0 <= \(m_i\) <= 1000000000).
Ваша программа должна вывести в стандартный вывод ровно одно целое число – количество всех неубывающих последовательностей целых чисел, для которых входная последовательность является средней последовательностью.
3 2 5 9
4