Hay Type Majority Conversion

Farmer John has an important task – to decide which type of hay to purchase so that all of his cows eventually like the same hay. He has N cows (2 \(\le N \le 10^5\)) numbered from 1 to N, and each cow initially likes exactly one type of hay \(h_i\) (1 \(\le h_i \le N\)).

In order to achieve a unanimous preference, Farmer John can host focus group interviews. In one interview, he selects a contiguous segment of cows (from index \(i\) to \(j\)). If there exists a hay type in that segment which is favored by more than half of the cows in that segment (i.e. strictly more than \(\frac{j-i+1}{2}\)), then after the interview every cow in the segment will change its preference to that hay type. Otherwise, no cow changes its preference.

Farmer John can host as many interviews as he needs (one at a time) to try to convert the herd so that ultimately every cow likes the same type of hay. Your task is to determine which hay types have the potential to become the unanimous choice.

Explanation: Note that a focus group with only one cow will always have a majority (since 1 > 0.5), but that interview does not help in conversion because it does not change any cow’s preference. Thus, to begin the conversion process, there must exist some contiguous segment of at least 2 cows in which a hay type is the majority. In other words, a hay type x can propagate if and only if there exists a contiguous segment (of length \(L \ge 2\)) where the number of cows that like hay type \(x\) is \(f\) and \(f > \frac{L}{2}\). It turns out that this condition is equivalent to the existence of two occurrences of x within distance at most 2 in the original sequence (i.e. either consecutive or with one cow in between).

For example:

• If \(N = 2\) and the preferences are [1, 2], no hay type appears twice close by, so no conversion is possible.
• If \(N = 3\) and the preferences are [1, 2, 1], hay type 1 appears at positions 1 and 3. In the segment [1, 3] the count of 1's is 2 and the segment length is 3 (2 > 1.5), so hay type 1 can eventually be made unanimous.
• If \(N = 4\) and the preferences are [1, 2, 2, 1], hay type 2 forms a contiguous block at positions 2 and 3 and can take over, while hay type 1 cannot.

Your program should output all the hay types (in increasing order) that can possibly become the universal choice. If none exists, output -1.

inputFormat

The first line contains an integer (N) (2 (\le N \le 10^5)), the number of cows. The second line contains (N) integers (h_1, h_2, \ldots, h_N) (1 (\le h_i \le N)), representing the initial hay type liked by each cow.

outputFormat

Output in one line the hay types that can eventually become the unanimous favorite, in increasing order separated by spaces. If no such hay type exists, print -1.

sample

2
1 2

-1