Universal Cup Judging System

Universal Cup

Süre Sınırı: 1.5 s Bellek Sınırı: 512 MB Toplam puan: 100 Hack'lenebilir ✓
İstatistikler

Definiamo $\operatorname{mex}(S)$ come il minimo intero non negativo che non è contenuto in $S$.

Mayoi Hachikuji ha un array $a$ composto da $n$ elementi che vorrebbe fosse ordinato in ordine non decrescente. Per farlo, può eseguire la seguente operazione un qualsiasi numero di volte (eventualmente zero):

  • Scegliere un intero $i \in [1, \operatorname{length}(a) - 2]$ e sostituire $a_i, a_{i+1}, a_{i+2}$ con il loro $\operatorname{mex}$. Si noti che dopo aver applicato questa operazione, la lunghezza dell'array diminuisce di $2$.

Trova il numero minimo di operazioni che Mayoi deve eseguire per rendere l'array ordinato in ordine non decrescente. Nel caso in cui sia impossibile farlo, stampa $-1$.

Input

La prima riga dell'input contiene l'intero $n$ ($2 \le n \le 5 \cdot 10^5$) — la lunghezza dell'array $a$.

La riga successiva contiene $n$ interi $a_i$ ($0 \le a_i \le 10^9$) — gli elementi dell'array $a$.

Output

Stampa un solo numero — la risposta al problema.

Esempi

Input di esempio 1

3
4 1 3

Output di esempio 1

1

Input di esempio 2

9
3 0 2 2 3 0 4 7 8

Output di esempio 2

2

Input di esempio 3

2
4 3

Output di esempio 3

-1

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
#1662EditorialOpenNew Editorial for Problem #14434louyuxuanView
#372EditorialOpen题解jianglyView

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.