Majority Opinion

Time limit2sMemory limit1024 MB

Summary

Given each cow's preferred hay type, list every type that all cows can be made to like using majority focus groups on contiguous ranges, or print -1.

Level: Medium7 of 10
Topics: Array, Divide and conquer, Greedy
Solved: No attempts yet

Problem

Farmer John needs to decide which type of hay to buy for his cows.

Farmer John has $N$ cows ( $2 \le N \le 10^5$ ) numbered 1 through $N$ . Each cow likes exactly one type of hay, and cow $i$ likes type $h_i$ ( $1 \le h_i \le N$ ). Farmer John wants all cows to like the same type of hay.

He can host focus groups. A focus group brings together the cows numbered $i$ through $j$ (inclusive) for one meeting. If more than half of the cows in the group like the same type of hay, then after the meeting, all cows in the group like that type. If no such type exists, no cow changes its preference. For example, in a group of 16 cows, at least 9 must share a preference for the rest to switch to it.

Farmer John wants to know which types of hay can be liked by all cows at the same time. He can host only one focus group at a time, but he can run as many as needed until all cows like the same type.

Input

The first line contains an integer $T$ ( $1 \le T \le 10$ ), the number of test cases.

Each test case has two lines. The first line contains $N$ . The second line contains $N$ integers $h_1, h_2, \ldots, h_N$ , the favorite types of hay of the cows in order.

The sum of $N$ over all test cases does not exceed $2 \cdot 10^5$ .

Output

Output $T$ lines, one for each test case.

If all cows can be made to like the same type of hay, print every such type in increasing order on one line, separated by single spaces. Otherwise, print $-1$ . Do not leave trailing spaces on any line.

Examples1

Example 1

Input

5
5
1 2 2 2 3
6
1 2 3 1 2 3
6
1 1 1 2 2 2
3
3 2 3
2
2 1

Expected output