迎接新年的一项传统是向天空发射烟花。通常,发射的烟花会垂直向上飞行一段时间,然后爆炸,分裂成几部分朝不同方向飞行。有时,这些部件在一段时间后也会爆炸,分裂成更多部件,等等。
生活在无限网格中的利马克只有一个烟花。烟花的行为用递归深度 n 和每个递归级别 t1、t2、...、tn 的持续时间来描述。一旦利马克在某个牢房中发射烟花,烟花就会开始向上移动。在覆盖 t1 细胞(包括起始细胞)后,它会爆炸并分裂成两部分,每部分都朝改变 45 度的方向移动(具体请参见下图)。因此,一个部分沿左上方向移动,而另一部分沿右上方向移动。每个部分在覆盖 t2 细胞后再次爆炸,分裂成两部分,移动方向再次改变 45 度。该过程一直持续到第 n 级递归,此时所有 2n - 1 个现有部件都会爆炸并消失,而不会创建新部件。经过几级递归后,某些部分可能会同时位于同一位置 - 这是允许的,并且这些部分不会崩溃。
在发射烟花之前,Limak 必须确保没有人站在烟花至少会访问一次的牢房中。你能数出这些细胞的数量吗?
输入
输入的第一行包含一个整数 n (1 ≤ n ≤ 30) — 递归的总深度。
第二行包含 n 个整数 t1, t2, ..., tn (1 ≤ ti ≤ 5)。在第 i 层,2i - 1 个零件中的每一个在爆炸前都会覆盖 ti 个单元。
输出
打印一个整数,表示烟花的任何部分至少访问一次的单元格数量。
示例
输入 #1
4 4 2 2 3
输出 #1
39
输入 #2
6 1 1 1 1 1 3
输出 #2
85
输入 #3
1 3
输出 #3
3
注意
对于第一个示例,下图显示了每级递归后的情况。利马克从最底部的红细胞发射烟花。它覆盖了 t1 = 4 个细胞(标记为红色),爆炸并分成两部分(它们的进一步运动标记为绿色)。所有爆炸都标有“X”字符。在最后一张图中,有 4 个红色、4 个绿色、8 个橙色和 23 个粉色单元格。因此,访问过的单元格总数为 4 + 4 + 8 + 23 = 39。
对于第二个示例,下图显示了第 4、5 和 6 级之后的情况。中间的图显示了下一层中所有部件将移动的方向。