문제
오름차순 수열 s1, ..., sn+1 (1≤i≤n에 대해 si≤si+1)이 있다고 하자. 이에 대한 mi=(si + si+1)/2로 정의되는 수열 수열 m1, ..., mn을 s의 평균값 수열이라고 한다. 가령, 수열 1, 2, 2, 4의 평균값 수열은 1.5, 2, 3이다. 따라서 평균값 수열의 값은 분수가 될 수도 있지만, 이번 문제에서는 평균값이 정확하게 정수로 떨어지는 경우만을 생각하기로 한다.
n개의 정수로 된 오름차순 수열 m1, ..., mn이 있을 때, 이 m을 평균값 수열로 갖는 원래 수열 s1, ..., sn+1은 몇 개나 존재할지 그 개수를 계산하는 프로그램을 작성하시오.
입력
첫째 줄에는 정수 n (2≤n≤5,000,000)이 있고, 다음에는 m1, ..., mn의 값을 의미하는 수가 한 줄에 하나씩 있다. (0≤mi≤109) 단, 테스트 케이스들의 절반은 n≤1,000이고 0≤mi≤20,000이다.
출력
평균값 수열이 입력으로 들어온 수열과 일치하는 원래 수열의 개수를 출력하면 된다.
예제
3
2
5
9
4
힌트
로그인해야 코드를 작성할 수 있어요.