เรานิยาม $\operatorname{mex}(S)$ เป็นจำนวนเต็มไม่ติดลบที่น้อยที่สุดที่ไม่ได้อยู่ในเซต $S$
Mayoi Hachikuji มีอาเรย์ $a$ ที่ประกอบด้วยสมาชิก $n$ ตัว ซึ่งเธอต้องการให้เรียงลำดับแบบไม่ลดลง เพื่อการนั้น เธอสามารถดำเนินการต่อไปนี้กี่ครั้งก็ได้ (อาจเป็นศูนย์ครั้ง):
- เลือกจำนวนเต็ม $i \in [1, \operatorname{length}(a) - 2]$ แล้วแทนที่ $a_i, a_{i+1}, a_{i+2}$ ด้วยค่า $\operatorname{mex}$ ของทั้งสามตัว สังเกตว่าหลังจากใช้การดำเนินการนี้ ความยาวของอาเรย์จะลดลง $2$
จงหาจำนวนครั้งของการดำเนินการที่น้อยที่สุดที่ Mayoi ต้องทำเพื่อให้อาเรย์เรียงลำดับแบบไม่ลดลง ในกรณีที่เป็นไปไม่ได้ ให้แสดงผล $-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