Problem1058--数字和

1058: 数字和

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 228  Solved: 61
[Submit] [Status] [Web Board] [Creator:]

Description

PIPI有一条纸带,上面有n个数字,第i个数字为Ai。 他想把纸带选三个位置p1, p2, p3(p1 < p2 < p3)把纸带剪成4个每条长度至少为1的4条纸带。 分别为[1, p1-1], [p1+1, p2-1], [p2+1, p3-1], [p3+1, n],使得4个部分中数字之和相等。

Input

多组输入 每组测试数据第一行输入一个n(7 ≤ n ≤ 105) 第二行n个数,第i个数为Ai(0 ≤ Ai ≤ 109),表示第i个数

Output

输出字典序最小的p1,p2,p3 如果不存在这种操作,输出-1

Sample Input

7
6 2 6 2 6 2 6
7
1 2 3 4 5 6 7

Sample Output

2 4 6
-1

Source/Category