На складе грузы уложены в одну ленту из n контейнеров. Для каждого контейнера известен его вес.

Кладовщик хочет разделить ленту ровно в одном месте между двумя соседними контейнерами так, чтобы слева осталась непустая начальная часть ленты, а справа — непустая оставшаяся часть.

Требуется найти минимально возможную абсолютную разность между суммарными весами левой и правой частей.

Входные данные

Первая строка содержит целое число n — количество контейнеров в ленте.

Вторая строка содержит n целых чисел a_i — веса контейнеров.

Выходные данные

Выведите одно целое число — минимальную абсолютную разность суммарных весов двух частей после одного разреза.

Ограничения

• 2 <= n <= 2 * 10^5
• -10^9 <= a_i <= 10^9

Ответ может не помещаться в 32-битный целочисленный тип.

Примеры

Пример 1

Входные данные

5
1 3 2 4 1

Выходные данные

1

Пояснение

Разрез после третьего элемента: 1+3+2=6 и 4+1=5, разность 1 — минимум.

Пример 2

Входные данные

2
1 1

Выходные данные

0