题目描述
有$n$个人正在排队办理业务，其中第$i$个人办理业务所需时间为$a_i$。现在有两个窗口开放办理该业务，为了防止排队时间过长，你可以将这$n$个人按给定顺序分成两个队伍，例如从第$i$个人处将队列分割，意味着将第$1$至第$i-1$个人分为第一列，第$i$至第$n$个人分至第二个队伍，且不允许有一个队伍为空。
请问，如何分割这个队伍，能够使得得到的两个队列的总等待时间相差最小？
输入
输入共两行：
第一行，一个正整数$n$
第二行，$n$个正整数$a_1,a_2,\ldots,a_n$
输出
输出分割后两个队伍等待时间差值的最小值。
样例输入输出
提示
对于$30\%$的数据，$1 \leq n \leq 100$
对于$70\%$的数据，$1 \leq n \leq 10^4$
对于$100\%$的数据，$1 \leq n \leq 10^5，1 \leq a_i \leq 10^4$
样例1说明:第2和第3个人之间分割，前两个人的等待时间为2，最后那个人的等待时间为100，则两队列等待时间相差98。
样例2说明:第4和第5个人之间分割，前四个人的等待时间为10，后两个人的等待时间为11，则两队列等待时间相差1。