평균값 수열

길이가 $n+1$인 비감소 정수 수열 $s_1, s_2, \ldots, s_{n+1}$ (모든 $1 \le i \le n$에 대해 $s_i \le s_{i+1}$)을 생각하자.

이 수열의 평균값 수열을 다음과 같이 정의한다. $1 \le i \le n$에 대하여 $m_i = \frac{s_i + s_{i+1}}{2}.$

예를 들어 $S = (1, 2, 2, 4)$이면 평균값 수열은 $M = \left(\frac{3}{2},\ 2,\ 3\right)$이다. 이처럼 평균값 수열의 원소는 정수가 아닐 수도 있지만, 이 문제에서는 평균값 수열의 모든 원소가 정수인 경우만 다룬다.

길이가 $n$인 비감소 평균값 수열 $m_1, m_2, \ldots, m_n$이 주어질 때, 이 수열을 평균값 수열로 가지는 정수 수열 $s_1, s_2, \ldots, s_{n+1}$의 개수를 구하여라.

첫째 줄에 평균값 수열의 길이 $n$이 주어진다. ($2 \le n \le 5\,000\,000$)

다음 $n$개의 줄에 평균값 수열의 원소 $m_i$가 순서대로 한 줄에 하나씩 주어진다. ($0 \le m_i \le 1\,000\,000\,000$, 수열은 비감소이다.)

주어진 수열을 평균값 수열로 가지는 정수 수열 $s$의 개수를 한 줄에 출력하여라.

첫 번째 예제($m = (2, 5, 9)$)에서는 다음 네 가지 수열만이 존재한다. $(2, 2, 8, 10),\quad (1, 3, 7, 11),\quad (0, 4, 6, 12),\quad (-1, 5, 5, 13).$