D. Алиса, Боб и конфеты
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В ряд выложены $$$n$$$ конфет, которые пронумерованы слева направо от $$$1$$$ до $$$n$$$. Размер $$$i$$$-й конфеты равен $$$a_i$$$.

Алиса и Боб играют в интересную и вкусную игру — они едят конфеты. Алиса будет есть конфеты слева направо, а Боб — справа налево. Игра заканчивается, когда все конфеты съедены.

Процесс состоит из ходов. Во время хода игрок съедает одну или более конфет со своей стороны (Алиса ест слева, Боб — справа). Первый ход делает Алиса. Во время первого хода она съест $$$1$$$ конфету (ее размер равен $$$a_1$$$). Затем каждый следующий ход стороны чередуются — то есть второй ход совершает Боб, затем Алиса, затем снова Боб и так далее.

На каждом ходу игрок считает суммарный размер конфет, съеденных за текущий ход. Как только это число становится строго больше, чем суммарный размер конфет, съеденных другим игроком на предыдущем ходу, текущий игрок завершает ход. Иными словами, на очередном ходу игрок ест наименьшее возможное количество конфет, при котором сумма размеров съеденных в этот ход конфет строго больше суммы размеров конфет, которые съел другой игрок на предыдущем ходу. Если конфет недостаточно, чтобы совершить ход таким образом, то игрок доедает все оставшиеся конфеты и игра заканчивается.

Например, если $$$n=11$$$ и $$$a=[3,1,4,1,5,9,2,6,5,3,5]$$$, то:

  • ход 1: Алиса съест одну конфету размера $$$3$$$ и последовательность конфет примет вид $$$[1,4,1,5,9,2,6,5,3,5]$$$;
  • ход 2: на предыдущем ходу Алиса съела $$$3$$$, значит, Боб должен съесть $$$4$$$ или более — Боб съест одну конфету размера $$$5$$$ и последовательность конфет примет вид $$$[1,4,1,5,9,2,6,5,3]$$$;
  • ход 3: на предыдущем ходу Боб съел $$$5$$$, значит, Алиса должна съесть $$$6$$$ или более — Алиса съест три конфеты суммарным размером $$$1+4+1=6$$$ и последовательность конфет примет вид $$$[5,9,2,6,5,3]$$$;
  • ход 4: на предыдущем ходу Алиса съела $$$6$$$, значит, Боб должен съесть $$$7$$$ или более — Боб съест две конфеты суммарным размером $$$3+5=8$$$ и последовательность конфет примет вид $$$[5,9,2,6]$$$;
  • ход 5: на предыдущем ходу Боб съел $$$8$$$, значит, Алиса должна съесть $$$9$$$ или более — на пятом ходу Алиса съест две конфеты суммарным размером $$$5+9=14$$$ и последовательность конфет примет вид $$$[2,6]$$$;
  • ход 6 (последний): на предыдущем ходу Алиса съела $$$14$$$, значит, Боб должен съесть $$$15$$$ или более — это невозможно, поэтому Боб съест две оставшиеся конфеты и игра закончится.

Выведите количество ходов в этой игре и два числа:

  • $$$a$$$ — суммарный размер всех конфет, съеденных Алисой за всю игру;
  • $$$b$$$ — суммарный размер всех конфет, съеденных Бобом за всю игру.
Входные данные

В первой строке записано целое число $$$t$$$ ($$$1 \le t \le 5000$$$) — количество наборов входных данных. Далее следуют описания $$$t$$$ наборов входных данных.

Каждый набор состоит из двух строк. В первой строке содержится целое число $$$n$$$ ($$$1 \le n \le 1000$$$) — количество конфет. Во второй строке содержится последовательность целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 1000$$$) — размеры конфет в порядке их расположения слева направо.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных в тесте не превосходит $$$2\cdot10^5$$$.

Выходные данные

Для каждого набора входных данных выведите три целых числа — количество ходов в игре и искомые величины $$$a$$$ и $$$b$$$.

Пример
Входные данные
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
Выходные данные
6 23 21
1 1000 0
2 1 2
6 45 46
2 2 1
3 4 2
4 4 3