A13166 | Beautiful Regional Contest

So the Beautiful Regional Contest (BeRC) has come to an end! $n$ students took part in the contest. The final standings are already known: the participant in the $i$ -th place solved $p_i$ problems. Since the participants are primarily sorted by the number of solved problems, then $p_1 \ge p_2 \ge \dots \ge p_n$ .

Help the jury distribute the gold, silver and bronze medals. Let their numbers be $g$ , $s$ and $b$ , respectively. Here is a list of requirements from the rules, which all must be satisfied:

- for each of the three types of medals, at least one medal must be awarded (that is, $g>0$ , $s>0$ and $b>0$ );
- the number of gold medals must be strictly less than the number of silver and the number of bronze (that is, $g<s$ and $g<b$ , but there are no requirements between $s$ and $b$ );
- each gold medalist must solve strictly more problems than any awarded with a silver medal;
- each silver medalist must solve strictly more problems than any awarded a bronze medal;
- each bronze medalist must solve strictly more problems than any participant not awarded a medal;
- the total number of medalists $g+s+b$ should not exceed half of all participants (for example, if $n=21$ , then you can award a maximum of $10$ participants, and if $n=26$ , then you can award a maximum of $13$ participants).

The jury wants to reward with medals the total maximal number participants (i.e. to maximize $g+s+b$ ) so that all of the items listed above are fulfilled. Help the jury find such a way to award medals.

The first line of the input contains an integer $t$ ( $1 \le t \le 10000$ ) — the number of test cases in the input. Then $t$ test cases follow.

The first line of a test case contains an integer $n$ ( $1 \le n \le 4\cdot10^5$ ) — the number of BeRC participants. The second line of a test case contains integers $p_1, p_2, \dots, p_n$ ( $0 \le p_i \le 10^6$ ), where $p_i$ is equal to the number of problems solved by the $i$ -th participant from the final standings. The values $p_i$ are sorted in non-increasing order, i.e. $p_1 \ge p_2 \ge \dots \ge p_n$ .

The sum of $n$ over all test cases in the input does not exceed $4\cdot10^5$ .

Print $t$ lines, the $j$ -th line should contain the answer to the $j$ -th test case.

The answer consists of three non-negative integers $g, s, b$ .

- Print $g=s=b=0$ if there is no way to reward participants with medals so that all requirements from the statement are satisfied at the same time.
- Otherwise, print three positive numbers $g, s, b$ — the possible number of gold, silver and bronze medals, respectively. The sum of $g+s+b$ should be the maximum possible. If there are several answers, print any of them.