נגדיר את $\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