Задача Gadget
Маленькій Оленці на день народження подарували коробку різнокольорових бусинок. Подарунок дівчинці так сподобався, що вона вирішила сплести з них феньку. Для цього всі бусинки необхідно викласти в ряд. Оленка розклала бусинки і пішла до школи, а тим часом молодший братик Вася переклав бусинки в оберненому порядку і нікому не сказав про це. Коли дівчинка повернулась, вона нічого не помітила, тому що порядок кольорів у ряду бусинок не змінився. Допоможіть Оленці і Васі визначити, яку найяскравішу бусинку можна покласти до середини феньки. Зауважимо, що крім подарованих, у Оленки таких бусинок немає.
Технічні умови.
Програма читає з клавіатури кількість бусинок N (1<=N<=1000) і далі через пропуск N чисел від 1 до 9 – кольори бусинок. Чим більше колір, тим бусинка яскравіша. Програма виводить на екран колір бусинки, яку Оленка поклала в середину. Якщо скласти феньку неможливо, програма повинна друкувати -1.
Приклади
Введення
6 1 1 2 2 2 2
Виведення
2
Введення
7 9 9 9 9 9 9 3
Виведення
3
Введення
9 1 1 1 2 2 2 3 3 3
Виведення
-1
Примітка. У першому прикладі можна скласти 1 2 2 2 2 1 або 2 1 2 2 1 2. Фенька 2 1 1 1 1 2 неправильна, бо в середині не найяскравіша бусинка.