Вот и подошел к концу 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\) строк, \(j\)-я строка должна содержать ответ на \(j\)-й набор входных данных.
Ответ состоит из трёх неотрицательных целых чисел \(g, s, b\).
- Выведите \(g=s=b=0\), если не существует способа наградить участников медалями, чтобы одновременно выполнялись все требования из условия.
- В противном случае выведите три положительных числа \(g, s, b\) — возможное количество золотых, серебряных и бронзовых медалей, соответственно. Сумма \(g+s+b\) должна быть максимально возможной. Если ответов несколько, то выведите любой из них.
Примечание
В первом тестовом случае можно наградить \(1\) золотой, \(2\) серебряными и \(3\) бронзовыми медалями участников. Тогда золотую медаль получит участник, решившая \(5\) задач, серебрянные медали получат участники, решившие \(4\) задачи, бронзовые медали получат участники решившие \(2\) или \(3\) задачи. Участники, решившие \(1\) задачу медаль не получат. Заметим, что все условия выполнены и раздать медали таким способом можно. Больше, чем \(6\) медалей выдать невозможно, потому что нельзя выдать больше чем половину от количества участников медалей. Ответ \(1\), \(3\), \(2\) также является верным в этом тестовом случае.
Во втором и третьем тестовых случаев нельзя так раздать медали, потому что медаль каждого достоинства должна получить хотя бы один участник, но количество выданных медалей не должно превышать половину от количества участников.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|