Лечебный смузи
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Зельда нашла Линка (ура!), но теперь ей нужно сварить лечебный смузи, чтобы нейтрализовать влияние черной магии и поправить здоровье друга.

Приготовление смузи — это огромный квест, перед началом которого Зельда выбирает $$$n$$$ ингредиентов, заданных числами от $$$0$$$ до $$$10^9$$$, и упорядочивает их в последовательность $$$a_i$$$. Разрешается брать повторяющиеся ингредиенты, то есть $$$a_i = a_j$$$.

Затем принцессе необходимо найти секретный ингредиент, номер которого вычисляется следующим образом:

  1. Для каждого $$$i$$$ от $$$1$$$ до $$$n$$$ для последовательности $$$a_1, \ldots, a_{i-1}, a_i$$$ определяется $$$b_i$$$ — минимальный номер ингредиента, которого в этой последовательности нет (обозначается как $$$\mathrm{mex}(a_1, \ldots, a_i)$$$). Например, $$$\mathrm{mex}(1, 7, 2, 2, 0, 5, 4) = 3$$$ и $$$\mathrm{mex}(1, 4, 5, 2, 3) = 0$$$.
  2. От полученной последовательности $$$b_1, \ldots, b_n$$$ также вычисляется mex.
  3. И полученное в итоге значение $$$\mathrm{mex}(b_1, \ldots, b_n)$$$ берется в качестве номера секретного ингредиента.

Зельда уже выбрала набор из $$$n$$$ ингредиентов, но заметила, что от их порядка может меняться номер секретного ингредиента. Известно, что чем больше его номер, тем более высокими целительными свойствами будет обладать смузи, приготовленный с его использованием.

Помогите принцессе упорядочить выбранные ингредиенты так, чтобы соответствующий полученной последовательности ингредиентов номер секретного ингредиента был как можно больше.

Входные данные

В первой строке ввода дано одно целое число $$$n$$$ — количество ингредиентов у Зельды $$$(1 \leq n \leq 2 \cdot 10^5)$$$.

Во второй строке перечислены $$$n$$$ целых чисел от $$$0$$$ до $$$10^9$$$ — номера этих ингредиентов.

Выходные данные

Выведите единственное целое число — максимальный возможный номер секретного ингредиента.

Примеры

Входные данные
5
1 1 0 2 5
Выходные данные
4
Входные данные
3
0 0 0
Выходные данные
0

Примечание

В первом примере один из способов упорядочить ингредиенты выглядит как $$$a = [5, 0, 1, 2, 1]$$$. В этом случае мы получим $$$b = [0, 1, 2, 3, 3]$$$, mex которого равен $$$4$$$.