题目描述

Snuke 和 Raccoon 有一叠共 $N$ 张卡牌。
从上到下第 $i$ 张卡牌上写着整数 $a_i$。

现在他们要分这叠卡牌：

• Snuke 先从牌堆顶部拿走若干张牌；
• 然后 Raccoon 拿走剩下的所有牌。

要求两个人都至少拿一张牌。

设 Snuke 拿到的所有卡牌上的整数之和为 $x$，Raccoon 拿到的所有卡牌上的整数之和为 $y$。

他们希望最小化 $|x-y|$。
请你求出这个最小可能值。

输入格式

第一行输入一个整数 $N(N<=200000)$。

第二行输入 $N$ 个整数 $a_1,a_2,\dots,a_N(a_i <=1000000)$。

输出格式

输出一个整数，表示 $|x-y|$ 的最小可能值。

输入输出样例 #1

输入

6
1 2 3 4 5 6

输出

1

输入输出样例 #2

输入

2
10 -10

输出

20