30011번 - 겹다각형의 각

문제

당신은 $N$개의 볼록다각형으로 이루어진 그림을 그려야 한다. 이 그림은 다음 세 조건을 만족해야 한다.

• $i$번째 다각형은 $A_i$개의 꼭짓점을 가져야 한다. $(1 \le i \le N)$
• $i+1$번째 다각형의 모든 꼭짓점은 $i$번째 다각형의 내부 또는 경계에 속해야 한다. $(1 \le i < N)$
• 두 개 이상의 다각형이 한 꼭짓점을 공유할 수 없다.

이때, $i$번째 다각형은 $i+1$번째 다각형보다 꼭짓점 수가 많거나 같다. 즉, 1ドル \le i < N$인 정수 $i$에 대해 $A_i \ge A_{i+1}$이다.

아래 그림은 $A=\{ 4, 4, 3 \}$일 때, 조건에 맞게 그린 도형과 조건에 맞지 않는 도형의 예이다.

당신은 그림의 점수가 최대가 되도록 그림을 그리려고 한다. 그림의 점수는 그림에 그려진 선분으로 만들어지는 180ドル ^\circ$ 미만의 각 중 다른 각을 완전히 포함하지 않는 것의 각도의 합으로 정의된다.

예를 들어, 다음 그림의 $\angle DBA$와 $\angle CBD$는 조건에 맞지만, $\angle CBA$는 $\angle DBA$와 $\angle CBD$를 포함하기 때문에 조건에 맞지 않는다.

조건에 맞춰서 도형을 그렸을 때 가능한 그림의 점수의 최댓값을 구해 보자.

입력

첫째 줄에 다각형의 수 $N$이 주어진다.

둘째 줄에 $N$개의 수 $A_1,ドル $A_2,ドル $\cdots,ドル $A_N$가 공백으로 구분되어 주어진다.

출력

첫째 줄에 가능한 그림의 점수의 최댓값을 출력한다.

제한

• 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)$

힌트