#DP0013. 最大和1

最大和1

Problem Description

给定一个序列 a[1],a[2],a[3]......a[n]a[1],a[2],a[3]......a[n],你的任务是计算其连续子段的最大和。例如,给定 (6,1,5,4,7)(6,-1,5,4,-7),该序列中的最大和为 6+(1)+5+4=146+(-1)+5+4=14

Input

第一行输入包含一个整数 T(1T10000)T(1≤T≤10000) 表示后续测试数据的组数。接下来 TT 行每行由一个整数 N(1N100000)N(1≤N≤100000) 开始,接下来 NN 个整数 Ai(1000Ai1000)A_i(-1000≤A_i≤1000)

每个测试点的 N2×105\sum N≤2×10^5

Output

对每组测试数据,输出最大的子段和、该子段的起点位置和终点位置。

如果存在多个子段,请输出起点位置最靠前的,如果仍有多个,请输出其中终点位置最靠前的。

Sample

2
5 6 -1 5 4 -7
7 0 6 -1 1 -6 7 -5
14 1 4
7 1 6