Задача 54. Многоугольник скул ≡

Условие

Пришла. Стоит. Ей восемнадцать лет.

 — Вам сколько лет?  — Ответила:  — Осьмнадцать. —

Многоугольник скул, локтей, колен.

Надменность, угловатость и косматость.

...

Белла Ахмадулина, "Пришла. Стоит. Ей восемнадцать лет...", 1974 г.

Художница-авангардистка Белла привыкла изображать человеческие лица на треугольной сетке в форме выпуклого многоугольника, его вершины совпадают с узлами, а стороны лежат на линиях сетки. Помогите Белле выяснить, хватит ли ей краски для портрета: по известным длинам сторон фигуры определите её площадь в единичных треугольниках.

Формат входных данных

Первая строка входного файла содержит натуральное число n — количество сторон, вторая строка — n натуральных чисел a_i — длины сторон многоугольника в порядке обхода. Гарантируется непротиворечивость входных данных.

Формат выходных данных

Выведите одно натуральное число — ответ на вопрос задачи.

Ограничения

3 ≤ n ≤ 6

1 ≤ a_i ≤ 10⁸

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Решения, верно работающие в случае n = 3, получат не менее 10 баллов.

Решения, верно работающие в случае n = 4, получат не менее 20 баллов.

Решения, верно работающие в случае n = 5, получат не менее 40 баллов.

Решения, верно работающие в случае n = 6, получат не менее 30 баллов.

Пояснение к примеру

Смотри рисунок.

Примеры тестов

6
4 1 3 3 2 2

35