A. Beautiful Regional Contest
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вот и подошел к концу Beautiful Regional Contest (BeRC)! В соревновании приняли участие $$$n$$$ студентов. Уже известна таблица финальных результатов — участник на $$$i$$$-м месте решил $$$p_i$$$ задач. Так как в первую очередь участники упорядочиваются по количеству решенных задач, то $$$p_1 \ge p_2 \ge \dots \ge p_n$$$.

Помогите жюри распределить золотые, серебряные и бронзовые медали. Пусть их количества равны $$$g$$$, $$$s$$$ и $$$b$$$, соответственно. Вот перечень требований из регламента, которые все должны быть удовлетворены:

  • для каждого из трёх достоинств медалей хотя бы одна медаль должна быть вручена (то есть $$$g>0$$$, $$$s>0$$$ и $$$b>0$$$);
  • количество золотых медалей должно быть строго меньше и количества серебряных и количества бронзовых (то есть $$$g<s$$$ и $$$g<b$$$, но требований между $$$s$$$ и $$$b$$$ нет);
  • каждый золотой медалист должен решить строго больше задач, чем любой награждённый серебряной медалью;
  • каждый серебряный медалист должен решить строго больше задач, чем любой награждённый бронзовой медалью;
  • каждый бронзовый медалист должен решить строго больше задач, чем любой не награждённый медалью участник;
  • суммарное количество медалистов $$$g+s+b$$$ не должно превышать половину всех участников (например, если $$$n=21$$$, то можно наградить максимум $$$10$$$ участников, а если $$$n=26$$$, то можно наградить максимум $$$13$$$ участников).

Жюри хочет наградить медалями суммарно наибольшее количество $$$g+s+b$$$ участников так, чтобы все перечисленные пункты выполнялись. Помогите жюри найти такой способ награждения медалями.

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

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

Первая строка набора входных данных содержит целое число $$$n$$$ ($$$1 \le n \le 4\cdot10^5$$$) — количество участников BeRC. Вторая строка набора содержит последовательность целых чисел $$$p_1, p_2, \dots, p_n$$$ ($$$0 \le p_i \le 10^6$$$), где $$$p_i$$$ равно количеству задач, решенных $$$i$$$-м участником из таблицы финальных результатов. Значения $$$p_i$$$ отсортированы по невозрастанию, то есть $$$p_1 \ge p_2 \ge \dots \ge p_n$$$.

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

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

Выведите $$$t$$$ строк, $$$j$$$-я строка должна содержать ответ на $$$j$$$-й набор входных данных.

Ответ состоит из трёх неотрицательных целых чисел $$$g, s, b$$$.

  • Выведите $$$g=s=b=0$$$, если не существует способа наградить участников медалями, чтобы одновременно выполнялись все требования из условия.
  • В противном случае выведите три положительных числа $$$g, s, b$$$ — возможное количество золотых, серебряных и бронзовых медалей, соответственно. Сумма $$$g+s+b$$$ должна быть максимально возможной. Если ответов несколько, то выведите любой из них.
Пример
Входные данные
5
12
5 4 4 3 2 2 1 1 1 1 1 1
4
4 3 2 1
1
1000000
20
20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
32
64 64 63 58 58 58 58 58 37 37 37 37 34 34 28 28 28 28 28 28 24 24 19 17 17 17 17 16 16 16 16 11
Выходные данные
1 2 3
0 0 0
0 0 0
2 5 3
2 6 6
Примечание

В первом тестовом случае можно наградить $$$1$$$ золотой, $$$2$$$ серебряными и $$$3$$$ бронзовыми медалями участников. Тогда золотую медаль получит участник, решившая $$$5$$$ задач, серебрянные медали получат участники, решившие $$$4$$$ задачи, бронзовые медали получат участники решившие $$$2$$$ или $$$3$$$ задачи. Участники, решившие $$$1$$$ задачу медаль не получат. Заметим, что все условия выполнены и раздать медали таким способом можно. Больше, чем $$$6$$$ медалей выдать невозможно, потому что нельзя выдать больше чем половину от количества участников медалей. Ответ $$$1$$$, $$$3$$$, $$$2$$$ также является верным в этом тестовом случае.

Во втором и третьем тестовых случаев нельзя так раздать медали, потому что медаль каждого достоинства должна получить хотя бы один участник, но количество выданных медалей не должно превышать половину от количества участников.