$\operatorname{mex}(S)$ деп $S$ жиынында жоқ ең кіші теріс емес бүтін санды анықтайық.
Маёй Хачикудзиде $n$ элементтен тұратын $a$ массиві бар, ол оны кемімейтін ретпен сұрыптағысы келеді. Ол үшін келесі амалды кез келген рет (мүмкін, нөл рет) орындай алады:
- $i \in [1, \operatorname{length}(a) - 2]$ бүтін санын таңдап, $a_i, a_{i+1}, a_{i+2}$ элементтерін олардың $\operatorname{mex}$ мәнімен алмастыру. Бұл амалды қолданғаннан кейін массивтің ұзындығы $2$-ге кемитініне назар аударыңыз.
Массивті кемімейтін ретпен сұрыптау үшін Маёй орындауы тиіс ең аз амалдар санын табыңыз. Егер бұл мүмкін болмаса, $-1$ шығарыңыз.
Кіріс деректер
Кірістің бірінші жолында $a$ массивінің ұзындығын білдіретін бүтін сан $n$ ($2 \le n \le 5 \cdot 10^5$) берілген.
Келесі жолда $a$ массивінің элементтерін білдіретін $n$ бүтін сан $a_i$ ($0 \le a_i \le 10^9$) берілген.
Шығыс деректер
Бір санды — есептің жауабын шығарыңыз.
Мысалдар
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