报数

成绩 0 开启时间 2012年10月5日 星期五 15:30
折扣 0.8 折扣时间 2012年10月5日 星期五 15:30
允许迟交 关闭时间 2012年10月5日 星期五 15:30

题目描述

     A营和B营之间不合已经是整个部队公开的了,所以他们没事就找对方麻烦。因为部队做集体训练,A营和B营很不幸分在了一组。。。所以又不安静了。。。

     A营和B营都要报数,但是他们报数都很有意思,假设A营报的数为一个非递减的整数序列S1S2S3,……,Sn+1Si<=Si+1)。而B营报的数为序列M1M2,…,MS的“M序列”,其中Mi=(Si+Si+1)/2

    例如,S=(1, 3, 3, 5),则M=(2, 3, 4)

    警官要求先报出M序列,B营当然不会放过这么好一个为难A营的机会,所以他们会一顿乱报,当然还是满足Si<=Si+1的。而你的任务就是帮助A营求出他们报数的S序列有多少种情况。  

输入数据

   第一行一个数n表示M的个数

    第二到N+1行每行一个数Mi

输出数据

   一个整数,表示A营有多少种报数方案

样例输入

3

2

5

9

 

样例输出

4

(存在如下四个报数方案满足要求:

22810

13711

04612

-15513。)

 

数据范围

50%的数据n<=1000mi<=20000

    100%的数据2<=n<=100000mi<=109.