Студенты Вася и Петя учатся в БГУ (Байтляндском Государственном Университете). На одной из перемен они решили перекусить и заказали пиццу. Пицца представляет собой круг некоторого радиуса. Пиццу доставили уже разрезанную на n кусков, i-й кусок представляет собой сектор с углом равным ai. Вася и Петя хотят разделить все куски на два непрерывных сектора так, чтобы разница углов этих секторов была минимальна. Углом сектора называется сумма углов всех кусков пиццы входящих в него. Обратите внимание, что один из секторов может быть пустым.
Первая строка содержит одно целое число n (1 ≤ n ≤ 360) — количество кусков, на которые разрезана пицца.
Во второй строке записаны n целых чисел ai (1 ≤ ai ≤ 360) — углы секторов, на которые разрезана пицца. Сумма всех ai равна 360.
Выведите одно целое число — минимально возможную разницу между углами секторов пиццы которые достанутся Васе и Пете.
4
90 90 90 90
0
3
100 100 160
40
1
360
360
4
170 30 150 10
0
В первом тесте Вася может взять 1 и 2 куски, а Петя 3 и 4. Тогда ответ равен |(90 + 90) - (90 + 90)| = 0.
Во третьем тесте есть только один кусок, который полностью достанется Васе или Пете. Поэтому ответ равен |360 - 0| = 360.
В четвертом тесте Вася может взять 1 и 4 куски, тогда Пете достанутся 2 и 3 куски. Ответ в этом случае равен |(170 + 10) - (30 + 150)| = 0.
Поясняющая картинка к четвертому тесту:
Красный и зеленый сектора состоят каждый из двух соседних кусков пиццы, поэтому Вася может взять зеленый сектор, а Петя красный.
| Codeforces Round 448 (Div. 2) |
|---|
| Закончено |
