Алиса и Боб заскучали во время длинной поездки на машине, и поэтому решили сыграть в игру. Из окна они видят проезжающие мимо машины разных цветов. Машины едут подряд одна за другой.
В игре следующие правила. Сначала Алиса выбирает некоторый цвет A, потом Боб выбирает некоторый цвет B (A ≠ B). После каждой машины они обновляют количество машин их выбранного цвета, проехавших мимо них. Назовем эти числа после i-й машины cntA(i) and cntB(i).
- Если cntA(i) > cntB(i) для каждого i, то побеждает Алиса.
- Если cntB(i) ≥ cntA(i) для каждого i, то побеждает Боб.
- В ином случае игра завершается ничьей.
Боб знает все цвета машин, которые проедут мимо них, и их порядок. Алиса уже выбрала цвет A, и Боб теперь хочет выбрать такой цвет B, что с ним он выиграет (ничья не считается победой). Помогите ему найти такой цвет.
Если существует несколько решений, то выведите любое из них. Если не существует ни одного такого цвета, то выведите -1.
Выходные данные
Выведите такой цвет B (1 ≤ B ≤ 106), что если Боб выберет его, то выиграет. Если существует несколько решений, то выведите любое из них. Если не существует ни одного такого цвета, то выведите -1.
Гарантируется, что если существует хотя бы одно решение, то существует также решение с (1 ≤ B ≤ 106).
Примечание
Рассмотрим доступность цветов в первом примере:
- cnt2(i) ≥ cnt1(i) для каждого i, соответственно, цвет 2 выигрышный.
- cnt4(2) < cnt1(2), поэтому цвет 4 не является выигрышным для Боба.
- Для всех остальных цветов cntj(2) < cnt1(2), поэтому они тоже недоступны.
В третьем примере любой цвет, кроме цвета 10, приемлем.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 1
2 1 4 2
|
2
|
|
2
|
5 2
2 2 4 5 3
|
-1
|
|
3
|
3 10
1 2 3
|
4
|