Fireworks

Time limit2sMemory limit1024 MB

Summary

A firework splits into two 45-degree branches after each vertical stage; count the distinct grid squares colored across all stages.

Level: Medium6 of 10
Topics: Simulation, DFS, Geometry, Implementation
Solved: No attempts yet

Problem

Modern fireworks rockets often consist of several stages. The first stage flies up a little and then bursts into smaller second-stage pieces, which after flying a bit farther may burst again.

Henrietta has just watched a fireworks display and now wants to draw a picture of it on grid paper. In the picture, the rocket's first stage flies straight up for a given number of squares and then splits in two. The two pieces spread apart at 45 degrees from their current direction, one to the left and one to the right. Each piece flies a little farther and may then split in two again in the same way.

The rocket always moves along the grid squares, and each stage colors every square it passes through (the launch point itself is not counted). While heading straight up it moves one square vertically at a time; after turning 45 degrees it moves one square diagonally at a time.

Before drawing the picture, Henrietta wants to know how many squares she must color in total. If a square is already colored and another rocket piece flies onto the same square, it does not need to be colored again (overlapping squares are counted only once).

Input

The first line contains the number of rocket stages $N$ ( $1 \le N \le 30$ ). The second line contains $N$ integers $A_i$ ( $1 \le A_i \le 5$ ), separated by spaces, giving how far each stage flies.

Output

Print, on a single line, the total number of squares that must be colored.

Examples3

Example 1
Input
```
1
3
```
Expected output
```
3
```
Example 2
Input
```
4
4 2 2 3
```
Expected output
```
39
```
Example 3
Input
```
6
1 1 1 1 1 3
```
Expected output
```
85
```