길이 n+1의 비감소 수열 s₁,...,s_n+1 (s_i ≤ s_i+1 for 1 ≤ i ≤ n) 을 생각해보자.

이러한 수열의 "평균값 수열"을 다음과 같이 정의한다 : 1 ≤ i ≤ n에서 m_i = (s_i + s_i+1)/2.

예를 들어, S = {1,2,2,4} 일 때 M = {3/2,2,3}이다. 이렇듯 평균값 수열은 정수가 아닌 수가 나올 수도 있지만, 이 문제에서는 평균값 수열의 원소가 정수인 경우만 고려하기로 한다.

길이 n의 감소하지 않는 평균값 수열 m₁,...,m_n이 주어질때, 해당 수열을 평균값 수열로 가지는 수열 s₁,...,s_n+1의 개수를 세어라.

입력 형식

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

이후 n개의 줄에 평균값 수열 m_i가 순서대로 주어진다. (0 ≤ m_i ≤ 1,000,000,000)

출력 형식

주어진 수열을 평균값 수열로 가지는 수열의 개수를 출력하라.

예제 입력

3
2
5
9

예제 출력

4

힌트

다음과 같은 4가지 경우만이 존재한다 : {2,2,8,10} / {1,3,7,11} / {0,4,6,12} / {-1,5,5,13}