Загублений олівець#11667

Загублений олівець

3 секунди

5 мегабайтів

Середня

Увага до обмеження за пам'яттю!

У колекції дядька є $n$ олівців, кожен з яких різного кольору. Кольори цих олівців виражені цілими числами від $1$ до $n$ . Втомившись грати зі своїми іграшками, Мюжган вирішила пограти цими олівцями. Погравши якийсь час, вона втратила один з олівців, але, щоб дядько не дізнався, вона поклала в колекцію один зі своїх олівців. Олівець, який вона поклала, має той же колір, що й втрачений олівець або інший олівець з цієї колекції. Якщо це олівець такого ж кольору, що і втрачений олівець, її дядько не дізнається, що олівець зник, інакше він не зможе не помітити втрати. Але чи зможете ви знайти втрачений олівець?

Вам дано кількість олівців у колекції дядька та стан олівців після того, як Мюжган додала олівець на заміну зниклому, тобто кольори олівців з колекції. Знайдіть колір олівця, який втратила Мюжган. Якщо це неможливо знайти точно, виведіть результат $- 1$ .

Вхідні дані

У першому рядку задається одне ціле число $n (2 \leq n \leq 2 \cdot 1 0^{6})$ n~(2 \le n \le 2 \cdot 10^6). Кожен з наступних $n$ рядків містить ціле число $c_{i} (1 \leq c_{i} \leq n)$ c_i~(1 \le c_i \le n) — кольори олівців.

Вихідні дані

Якщо точно можливо знайти олівець, який втратила Мюжган, виведіть в результаті колір цього олівця, в іншому випадку виведіть $- 1$ .

Приклади

Тест 1. Колір втраченого олівця — $1$ , і Мюжган замінила його олівцем кольору $2$ .

Тест 2. Мюжган дуже добре впоралась із заміною втраченого олівця :).

Приклад 1

Приклад 2