لنعرّف $\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