Визначимо $\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