说明

有n个人正在排队办理业务，其中第i个人办理业务所需时间为ai。现在有两个窗口开放办理该业务，为了防止排队时间过长，你可以将这n个人按给定顺序分成两个队伍，例如从第i个人处将队列分割，意味着将第1至第i-1个人分为第一列，第i至第n个人分至第二个队伍，且不允许有一个队伍为空。

请问，如何分割这个队伍，能够使得得到的两个队列的总等待时间相差最小？

输入格式

第一行，一个正整数n 第二行，n个正整数a1,a2,…,an

输出格式

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

3
1 1 100

98

提示

【样例1解释】

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

【输入样例2】

6

1 2 3 4 5 6

【输出样例2】

1

【样例2解释】

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

【数据范围】

1<=n<=100000，1<=ai<=100000。

来源

前缀和