Определим $\operatorname{mex}(S)$ как минимальное неотрицательное целое число, которое не содержится в $S$.
У Маёй Хатикудзи есть массив $a$, состоящий из $n$ элементов, который она хочет отсортировать в порядке неубывания. Для этого она может выполнить следующую операцию любое количество раз (возможно, ноль):
- Выбрать целое число $i \in [1, \operatorname{length}(a) - 2]$ и заменить $a_i, a_{i+1}, a_{i+2}$ на их $\operatorname{mex}$. Обратите внимание, что после применения этой операции длина массива уменьшается на $2$.
Найдите минимальное количество операций, которое необходимо выполнить Маёй, чтобы сделать массив отсортированным по неубыванию. Если это невозможно, выведите $-1$.
Входные данные
Первая строка входных данных содержит целое число $n$ ($2 \le n \le 5 \cdot 10^5$) — длину массива $a$.
Следующая строка содержит $n$ целых чисел $a_i$ ($0 \le a_i \le 10^9$) — элементы массива $a$.
Выходные данные
Выведите одно число — ответ на задачу.
Примеры
Пример входных данных 1
3 4 1 3
Пример выходных данных 1
1
Пример входных данных 2
9 3 0 2 2 3 0 4 7 8
Пример выходных данных 2
2
Пример входных данных 3
2 4 3
Пример выходных данных 3
-1