4433: New Year and Fireworks
内存限制：256 MB
时间限制：2 S
题面：传统
评测方式：文本比较
上传者：
提交：3
通过：2
题目描述
D. New Year and Fireworks
time limit per test
2.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
One tradition of welcoming the New Year is launching fireworks into the sky. Usually a launched firework flies vertically upward for some period of time, then explodes, splitting into several parts flying in different directions. Sometimes those parts also explode after some period of time, splitting into even more parts, and so on.
Limak, who lives in an infinite grid, has a single firework. The behaviour of the firework is described with a recursion depth n and a duration for each level of recursion t1,t2,...,tn. Once Limak launches the firework in some cell, the firework starts moving upward. After covering t1 cells (including the starting cell), it explodes and splits into two parts, each moving in the direction changed by 45 degrees (see the pictures below for clarification). So, one part moves in the top-left direction, while the other one moves in the top-right direction. Each part explodes again after covering t2 cells, splitting into two parts moving in directions again changed by 45 degrees. The process continues till the n-th level of recursion, when all 2n-1 existing parts explode and disappear without creating new parts. After a few levels of recursion, it's possible that some parts will be at the same place and at the same time− it is allowed and such parts do not crash.
Before launching the firework, Limak must make sure that nobody stands in cells which will be visited at least once by the firework. Can you count the number of those cells?
Limak, who lives in an infinite grid, has a single firework. The behaviour of the firework is described with a recursion depth n and a duration for each level of recursion t1,t2,...,tn. Once Limak launches the firework in some cell, the firework starts moving upward. After covering t1 cells (including the starting cell), it explodes and splits into two parts, each moving in the direction changed by 45 degrees (see the pictures below for clarification). So, one part moves in the top-left direction, while the other one moves in the top-right direction. Each part explodes again after covering t2 cells, splitting into two parts moving in directions again changed by 45 degrees. The process continues till the n-th level of recursion, when all 2n-1 existing parts explode and disappear without creating new parts. After a few levels of recursion, it's possible that some parts will be at the same place and at the same time− it is allowed and such parts do not crash.
Before launching the firework, Limak must make sure that nobody stands in cells which will be visited at least once by the firework. Can you count the number of those cells?
Input
The first line of the input contains a single integer n (1≤n≤30)− the total depth of the recursion.The second line contains n integers t1,t2,...,tn (1≤ti≤5). On the i-th level each of 2i-1 parts will cover ti cells before exploding.
Output
Print one integer, denoting the number of cells which will be visited at least once by any part of the firework.
Examples
Input
4 4 2 2 3
Output
39
Input
6 1 1 1 1 1 3
Output
85
Input
1 3
Output
3
Note
For the first sample, the drawings below show the situation after each level of recursion. Limak launched the firework from the bottom-most red cell. It covered t1=4 cells (marked red), exploded and divided into two parts (their further movement is marked green). All explosions are marked with an 'X' character. On the last drawing, there are 4 red, 4 green, 8 orange and 23 pink cells. So, the total number of visited cells is 4+4+8+23=39.
For the second sample, the drawings below show the situation after levels 4, 5 and 6. The middle drawing shows directions of all parts that will move in the next level.
迎接新年的一个传统是向天空发射烟花。通常，发射的烟花会垂直向上飞行一段时间，然后爆炸，分裂成不同方向飞行的几个部分。有时这些部分在一段时间后也会爆炸，分裂成更多的部分，等等。
生活在无限网格中的Limak只有一支烟花。烟花的行为用递归深度n和递归t1、t2、…的每一级的持续时间来描述，。。。，一旦Limak在某个牢房发射烟花，烟花就开始向上移动。在覆盖t1细胞（包括起始细胞）后，它爆炸并分裂成两部分，每个部分都以45度的方向移动（请参见下面的图片进行说明）。因此，一个部分沿左上方向移动，而另一个部分则沿右上方向移动。每个部分在覆盖t2细胞后再次爆炸，分成两部分，方向再次改变45度。该过程一直持续到第n级递归，此时所有2n-1个现有部件都会爆炸并消失，而不会创建新部件。经过几级递归后，某些部分可能会在同一时间和同一地点，这是允许的，并且这些部分不会崩溃。
在燃放烟花之前，Limak必须确保没有人站在牢房中，因为烟花至少会造访牢房一次。你能数一下这些细胞的数量吗？
输入格式
输入的第一行包含单个整数n（1≤n≤30）−递归的总深度。
第二行包含n个整数t1，t2，。。。，tn（1≤ti≤5）。在第i层，每一个2i-1部件将在爆炸前覆盖钛电池。
第二行包含n个整数t1，t2，。。。，tn（1≤ti≤5）。在第i层，每一个2i-1部件将在爆炸前覆盖钛电池。
输出格式
打印一个整数，表示烟花的任何部分将至少访问一次的单元格数。
输入样例 复制
4
4 2 2 3输出样例 复制
39数据范围与提示
对于第一个示例，下图显示了每个递归级别之后的情况。利马克从最下面的红细胞发射了烟花。它覆盖了t1=4个细胞（标记为红色），分解并分成两部分（它们的进一步移动标记为绿色）。所有爆炸都标有“X”字符。在最后一张图上，有4个红色、4个绿色、8个橙色和23个粉色单元格。因此，访问的小区总数为4+4+8+23=39。
对于第二个示例，下图显示了级别4、5和6之后的情况。中间的图形显示了将在下一级移动的所有零件的方向
对于第二个示例，下图显示了级别4、5和6之后的情况。中间的图形显示了将在下一级移动的所有零件的方向