Angles of Overlapping Polygons

Time limit1sMemory limit1024 MB

Summary

Given nested convex polygons with non-increasing vertex counts A_i, find the maximum sum of counted angles in a valid figure.

Level: Medium7 of 10
Topics: Geometry, Math, Greedy
Solved: No attempts yet

Problem

You must draw a figure made of $N$ convex polygons. The figure must satisfy the following three conditions.

The $i$ -th polygon has $A_i$ vertices. ( $1 \le i \le N$ )
Every vertex of the $(i+1)$ -th polygon lies inside or on the boundary of the $i$ -th polygon. ( $1 \le i < N$ )
No two or more polygons may share a vertex.

The $i$ -th polygon has at least as many vertices as the $(i+1)$ -th polygon. That is, $A_i \ge A_{i+1}$ for every integer $i$ with $1 \le i < N$ .

The figure below shows a valid and an invalid drawing when $A=\{ 4, 4, 3 \}$ .



Valid figure	Invalid figure

You want the score of the figure to be as large as possible. The score is the sum of the angles, each less than $180^\circ$ , formed by the line segments drawn in the figure, counting only those angles that do not fully contain another angle.

For example, $\angle DBA$ and $\angle CBD$ in the figure above are valid. $\angle CBA$ is not valid, because it contains both $\angle DBA$ and $\angle CBD$ .

Find the maximum score that a valid figure can have.

Input

The first line contains the number of polygons $N$ .

The second line contains $N$ integers $A_1, A_2, \cdots, A_N$ separated by spaces.

Output

Print the maximum score of a valid figure on the first line.

Constraints

$1 \leq N \leq 1\,000$
$3 \leq A_i \leq 100$ $(1 \leq i \leq N)$
$A_i \ge A_{i+1}$ $(1 \leq i < N)$

Examples3

Example 1
Input
```
1
4
```
Expected output
```
360
```
Example 2
Input
```
2
4 3
```
Expected output
```
900
```
Example 3
Input
```
3
4 4 3
```
Expected output
```
1620
```