You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

合理分配

今年，岐麦王国的西瓜大丰收啦！

装满西瓜的 $n$ 辆车依次停在了城堡前，每辆车上西瓜的总重量分别为 $a_1, a_2, \dots, a_n$，国王决定把车队从中间一分为二，分别把西瓜运送给下属的两个城镇居民，同时为了公平起见，他想让两个城镇分得的西瓜的总重量差值最小，请聪明的你帮国王分一分吧，并且输出这个最小的差值。

注意：每辆车的西瓜不能相互转移，并且车队的次序不能打乱。

输入格式

• 第一行：单个整数 $n$
• 第二行：$n$ 个整数 $a_1, a_2, \dots, a_n$

输出格式

• 单个整数：表示两个城镇分得的西瓜总重量的最小差值

输入输出样例

3
100 1 1

98

6
1 2 3 4 5 6

1

数据范围

$1 \leq n \leq 100000$ ；

$1 \leq a_i \leq 10000$ 。