Description
Yoshiko wants to plant bananas on her farm, but it has been infected by a tentacle monster. Naturally, she wants to kill it first; now she wonders, exactly how much persticide should she buy to destroy every part of the monster.
The tentacle monster grows in the following way:
Assume that on an infinite 2D grid, a single monster spore spawns in the cell (0,0), it will at first grow upward, occupying p1 cells.
and then its growth splits into two directions: one moving +45 degrees and the other -45 degrees away from the original direction.
The monster proceeds to grow recursively: on the i-th day, extends pi cells, splits into two directions, and so on. A cell may be occupied more than once, and it will not affect the monster’s growth.
Given the number of days passed N and the extension length on day 1...N, you are to calculate how many cells have been occupied.
Note that if a cell is occupied more than once, it is still included only once in the answer.
Sample test case illustrated on a grid:
Input
Each input file contains only one testcase. On each testcase, there will be only two lines: A single integer N on the first line, followed by another line of N integers p1, p2 ... pN.
1 <= N <= 30
1 <= pi <= 5 for i = 1...N
Output
For each testcase, output a single integer: how many cells have been occupied.