408459: GYM103134 D Corona Mashup

Like any very organized group, MaratonUSP likes to prepare well in advance. Thus, Lamarca was in charge of organizing a mashup for the next $$$ 10 ^ {18} $$$ days. As it is a team contest, and no team wants to be harmed by having few competitors, the number of people who will participate in the contest must be a multiple of $$$ 3 $$$.

Lamarca created a poll on Telegram for the next $$$ 10 ^ {18} $$$ days, but he forgot to allow participants to vote on multiple options. However, when talking to each other, people realized that everyone who could participate in a $$$ x $$$ day could also participate in every day after $$$ x $$$.

When choosing a date, ALL people who can participate on that day will show up, but if the number of people is not a multiple of $$$ 3 $$$, a team will be sad and there will be total chaos. Clearly, Lamarca does not want chaos and would also like to choose the best day for Mashup.

Help Lamarca discover this day! The best day is the day when the greatest number of people go and the contest still happens, that is, the day when the greatest number of people goes and that no team is sad. Or say if there is no date with these characteristics.

The first line contains a single integer $$$ N $$$ $$$ (3 \leq N \leq 10 ^ 6) $$$ ─ representing the number of contest participants.

The second contains $$$ N $$$ integers $$$ a_i $$$ $$$ (1 \leq a_i \leq 10 ^ {18}) $$$ ─ $$$ a_i $$$ represents the date from which the $$$ i $$$-th member of MaratonUSP can participate in the mashup.

Print a single integer $$$ D $$$, the best day for the contest. If you do not have a valid date, print $$$ -1 $$$.

8
1 9 4 7 8 4 9 9

4

4
1 2 3 3

-1