Mari kita definisikan $\operatorname{mex}(S)$ sebagai bilangan bulat tak negatif terkecil yang tidak terdapat di dalam $S$.
Mayoi Hachikuji memiliki sebuah larik $a$ yang terdiri dari $n$ elemen yang ingin ia urutkan dalam urutan tak menurun. Untuk melakukan hal tersebut, ia dapat melakukan operasi berikut berapa kali pun (mungkin nol kali):
- Pilih bilangan bulat $i \in [1, \operatorname{length}(a) - 2]$ dan ganti $a_i, a_{i+1}, a_{i+2}$ dengan nilai $\operatorname{mex}$ ketiganya. Perhatikan bahwa setelah menerapkan operasi ini, panjang larik berkurang sebesar $2$.
Carilah jumlah operasi minimum yang perlu dilakukan Mayoi agar larik tersebut terurut dalam urutan tak menurun. Apabila hal tersebut tidak mungkin dilakukan, keluarkan $-1$.
Masukan
Baris pertama masukan berisi bilangan bulat $n$ ($2 \le n \le 5 \cdot 10^5$) — panjang larik $a$.
Baris berikutnya berisi $n$ bilangan bulat $a_i$ ($0 \le a_i \le 10^9$) — elemen-elemen dari larik $a$.
Keluaran
Keluarkan satu bilangan — jawaban dari persoalan ini.
Contoh
Contoh Masukan 1
3 4 1 3
Contoh Keluaran 1
1
Contoh Masukan 2
9 3 0 2 2 3 0 4 7 8
Contoh Keluaran 2
2
Contoh Masukan 3
2 4 3
Contoh Keluaran 3
-1