750_D. New Year and Fireworks_36777
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?

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.

<image>

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.

<image>
def next(dx, dy):
    return ([(dx,dy+1), (dx, dy-1)] if dy == 0 else [(dx+1,dy), (dx-1, dy)] if dx * dy == 0 else [(dx,0), (0, dy)])
visited = set()
states = set()
n = int(raw_input())
T = map(int, raw_input().split())
states.add((0,0,0,1))
for t in T:
    new_states = set()
    for x,y,dx,dy in states:
        cnt = 0
        for k in range(1, t + 1):
            visited.add((x + k * dx, y + k * dy))
            cnt += 1
        next_dirs = next(dx, dy)
        for ndx, ndy in next_dirs:
            new_states.add((x + t*dx, y + t*dy, ndx, ndy))
    states = new_states
print len(visited)

6
1 1 1 1 1 3
 1
3
 4
4 2 2 3
 30
4 1 3 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5
 4
4 2 4 1
 30
1 3 4 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5
 30
2 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5
 20
4 5 3 4 5 4 2 4 2 1 5 3 3 1 4 1 2 4 4 3
 1
1
 30
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
 11
5 5 5 5 5 5 5 5 5 4 4
 5
5 5 5 5 5
 30
1 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5
 7
5 3 3 5 5 4 4
 30
5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
 8
3 3 3 3 3 3 3 1
 5
2 2 5 3 1
 30
5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5
 29
3 1 3 3 1 2 2 3 5 3 2 2 3 2 5 2 3 1 5 4 3 4 1 3 3 3 4 4 4
 30
4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
 10
1 3 1 4 2 2 2 5 2 3
 28
1 3 4 4 4 3 1 4 5 1 3 5 3 2 5 1 4 4 5 3 4 2 5 4 2 5 3 2
 8
3 3 3 3 5 5 5 5
 10
2 3 4 2 1 2 3 4 2 1
 3
5 3 3
 30
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
 1
4
 30
5 5 1 1 4 4 3 1 5 3 5 5 1 2 2 3 4 5 2 1 4 3 1 1 4 5 4 4 2 2
 15
4 4 4 3 2 1 5 3 5 3 4 1 2 4 4
 2
5 5
 30
1 3 4 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
 30
2 5 4 3 2 3 4 2 4 4 1 2 1 2 4 4 1 3 3 2 1 5 4 2 2 2 1 5 2 4
 19
5 1 2 1 1 2 1 2 1 2 1 2 1 2 5 5 5 5 5
 5
1 2 3 4 5
 30
1 4 5 3 3 3 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5
 5
5 4 3 2 1
 3
1 1 1
 30
4 1 3 5 5 5 5 5 5 5 5 5 5 5 5 5 4 5 5 5 5 5 5 5 5 5 5 5 5 5
 30
2 5 5 5 5 5 5 5 5 5 5 5 2 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5
 20
4 5 3 4 5 4 2 4 2 1 5 3 3 1 4 1 2 4 4 4
 30
2 2 2 2 2 2 2 2 2 2 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
 30
1 5 5 5 5 5 5 5 4 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5
 7
5 3 3 5 1 4 4
 30
5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1
 8
3 4 3 3 3 3 3 1
 30
5 5 5 5 5 5 5 5 5 1 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5
 30
4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 2 4 4 4 4 4 4 4 4 4
 30
1 3 4 3 3 3 3 3 1 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
 19
5 1 2 1 1 2 1 2 1 2 1 2 1 2 5 5 5 5 3
 5
2 2 3 4 5
 5
5 4 3 3 1
 6
1 1 1 2 1 3
 1
2
 4
4 4 2 3
 20
4 5 3 4 5 4 2 4 2 1 5 3 3 1 4 1 4 4 4 4
 30
2 2 2 2 2 2 2 2 2 2 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 2 2 2
 30
5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 1 1 1 1 1 1 1 1 1 1
 8
3 4 3 5 3 3 3 1
 30
5 5 5 5 5 5 5 5 5 1 5 5 5 5 5 5 5 5 5 2 5 5 5 5 5 5 5 5 5 5
 30
1 3 4 3 3 3 3 3 1 3 3 3 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
 19
5 1 2 1 1 2 2 2 1 2 1 2 1 2 5 5 5 5 3
 5
2 2 4 4 5
 5
5 4 3 3 2
 6
1 1 1 4 1 3
 4
4 4 3 3
 30
2 2 2 2 2 2 2 2 2 2 1 2 2 2 2 2 2 2 2 2 2 4 2 2 2 2 1 2 2 2
 8
3 4 3 5 3 3 2 1
 19
5 1 2 1 1 2 2 2 1 2 1 2 1 2 5 5 5 5 1
 6
1 1 2 4 1 3
 4
4 4 3 4
 30
2 2 2 2 2 2 2 2 2 2 1 1 2 2 2 2 2 2 2 2 2 4 2 2 2 2 1 2 2 2
 6
1 2 2 4 1 3
 30
2 2 2 2 3 2 2 2 2 2 1 1 2 2 2 2 2 2 2 2 2 4 2 2 2 2 1 2 2 2
 30
2 2 2 2 3 2 2 2 2 2 2 1 2 2 2 2 2 2 2 2 2 4 2 2 2 2 1 2 2 2
 30
2 2 2 2 3 2 2 2 2 2 2 1 2 4 2 2 2 2 2 2 2 4 2 2 2 2 1 2 2 2
 30
2 2 2 2 3 2 2 2 2 2 2 1 2 4 2 1 2 2 2 2 2 4 2 2 2 2 1 2 2 2
 30
2 2 2 2 3 2 2 2 2 2 1 1 2 4 2 1 2 2 2 2 2 4 2 2 2 2 1 2 2 2
 30
2 3 2 2 3 2 2 2 2 2 1 1 2 4 2 1 2 2 2 2 2 4 2 2 2 2 1 2 2 2
 4
4 4 4 1
 30
1 3 4 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 1 5

85
 3
 39
 60096
 32
 61237
 43348
 10495
 1
 10479
 3544
 147
 43348
 480
 2744
 384
 65
 43348
 21903
 30781
 1145
 26461
 905
 928
 23
 2744
 4
 24339
 5661
 15
 23706
 21249
 6535
 122
 59453
 57
 7
 60616 60991 10726 10361 62027 396 2970 399 60014 39965 23363 6019 123 64 100 2 44 11402 10033 3150 431 59004 23083 6275 127 78 121 48 10897 385 5767 133 55 10679 139 11019 11363 12283 11819 11467 11687 36 58940