题目描述

有n个人正在排队办理业务，其中第i个人办理业务所需时间为ai。现在有两个窗口开放办理该业务，为了防止排队时间过长，你可以将这n个人按给定顺序分成两个队伍，例如从第i个人处将队列分割，意味着将第1至第i−1个人分为第一列，第i至第n个人分至第二个队伍，且不允许有一个队伍为空。
请问，如何分割这个队伍，能够使得得到的两个队列的总等待时间相差最小？

输入格式

输入共两行：
第一行，一个正整数n
第二行，n个正整数a1,a2,…,an

输出格式

输出分割后两个队伍等待时间差值的最小值。

数据范围

对于30%的数据，1≤n≤100
对于70%的数据，1≤n≤1000
对于100%的数据，1≤n≤100000，1≤ai≤10000

样例数据

输入:

3

1 1 100

输出:

98

说明:

第2和第3个人之间分割，前两个人的等待时间为2，最后那个人的等待时间为100，则两队列等待时间相差98。

输入:

6

1 2 3 4 5 6

输出:

1

说明:

第4和第5个人之间分割，前四个人的等待时间为10，后两个人的等待时间为11，则两队列等待时间相差1。