D. Alice, Bob and Candies

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

There are nn candies in a row, they are numbered from left to right from 11 to nn. The size of the ii-th candy is aiai.

Alice and Bob play an interesting and tasty game: they eat candy. Alice will eat candy from left to right, and Bob — from right to left. The game ends if all the candies are eaten.

The process consists of moves. During a move, the player eats one or more sweets from her/his side (Alice eats from the left, Bob — from the right).

Alice makes the first move. During the first move, she will eat 11 candy (its size is a1a1). Then, each successive move the players alternate — that is, Bob makes the second move, then Alice, then again Bob and so on.

On each move, a player counts the total size of candies eaten during the current move. Once this number becomes strictly greater than the total size of candies eaten by the other player on their previous move, the current player stops eating and the move ends. In other words, on a move, a player eats the smallest possible number of candies such that the sum of the sizes of candies eaten on this move is strictly greater than the sum of the sizes of candies that the other player ate on the previous move. If there are not enough candies to make a move this way, then the player eats up all the remaining candies and the game ends.

For example, if n=11n=11 and a=[3,1,4,1,5,9,2,6,5,3,5]a=[3,1,4,1,5,9,2,6,5,3,5], then:

• move 1: Alice eats one candy of size 33 and the sequence of candies becomes [1,4,1,5,9,2,6,5,3,5][1,4,1,5,9,2,6,5,3,5].
• move 2: Alice ate 33 on the previous move, which means Bob must eat 44 or more. Bob eats one candy of size 55 and the sequence of candies becomes [1,4,1,5,9,2,6,5,3][1,4,1,5,9,2,6,5,3].
• move 3: Bob ate 55 on the previous move, which means Alice must eat 66 or more. Alice eats three candies with the total size of 1+4+1=61+4+1=6 and the sequence of candies becomes [5,9,2,6,5,3][5,9,2,6,5,3].
• move 4: Alice ate 66 on the previous move, which means Bob must eat 77 or more. Bob eats two candies with the total size of 3+5=83+5=8 and the sequence of candies becomes [5,9,2,6][5,9,2,6].
• move 5: Bob ate 88 on the previous move, which means Alice must eat 99 or more. Alice eats two candies with the total size of 5+9=145+9=14 and the sequence of candies becomes [2,6][2,6].
• move 6 (the last): Alice ate 1414 on the previous move, which means Bob must eat 1515 or more. It is impossible, so Bob eats the two remaining candies and the game ends.

Print the number of moves in the game and two numbers:

• aa — the total size of all sweets eaten by Alice during the game;
• bb — the total size of all sweets eaten by Bob during the game.

Input

The first line contains an integer tt (1≤t≤50001≤t≤5000) — the number of test cases in the input. The following are descriptions of the tt test cases.

Each test case consists of two lines. The first line contains an integer nn (1≤n≤10001≤n≤1000) — the number of candies. The second line contains a sequence of integers a1,a2,…,ana1,a2,…,an (1≤ai≤10001≤ai≤1000) — the sizes of candies in the order they are arranged from left to right.

It is guaranteed that the sum of the values of nn for all sets of input data in a test does not exceed 2⋅1052⋅105.

Output

For each set of input data print three integers — the number of moves in the game and the required values aa and bb.

Example

input

Copy

7
11
3 1 4 1 5 9 2 6 5 3 5
1
1000
3
1 1 1
13
1 2 3 4 5 6 7 8 9 10 11 12 13
2
2 1
6
1 1 1 1 1 1
7
1 1 1 1 1 1 1

output

Copy

6 23 21
1 1000 0
2 1 2
6 45 46
2 2 1
3 4 2
4 4 3

 

解题说明：此题是一道模拟题，根据题目意思进行求解即可。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>

using namespace std;

int main()
{
	int t, p, j, u, i, t1, p1;
	scanf("%d", &t1);
	for (p1 = 1; p1 <= t1; p1++)
	{
		int n, suma = 0, sumb = 0, num = 0;
		int sweet[1009];
		scanf("%d", &n);
		for (i = 1; i <= n; i++)
		{
			scanf("%d", &sweet[i]);
		}
		t = 0;
		for (i = 1, j = n;;)
		{
			if (j < i)
			{
				break;
			}
			u = sweet[i++];
			while (u <= t && i <= j) 
			{
				u += sweet[i++];
			}
			suma += u;
			t = u;
			num++;
			if (j < i)
			{
				break;
			}
			u = sweet[j--];
			while (u <= t & i <= j) 
			{
				u += sweet[j--];
			}
			sumb += u;
			t = u;
			num++;
		}
		printf("%d %d %d\n", num, suma, sumb);
	}
	return 0;
}