Universal Cup Judging System

Universal Cup

حد الوقت: 1.5 s حد الذاكرة: 512 MB مجموع النقاط: 100 قابلة للهجوم ✓
الإحصائيات

Wir definieren $\operatorname{mex}(S)$ als die kleinste nichtnegative ganze Zahl, die nicht in $S$ enthalten ist.

Mayoi Hachikuji hat ein Array $a$ bestehend aus $n$ Elementen, das sie in nichtfallender Reihenfolge sortieren möchte. Dazu kann sie die folgende Operation beliebig oft (möglicherweise nullmal) ausführen:

  • Wähle eine ganze Zahl $i \in [1, \operatorname{length}(a) - 2]$ und ersetze $a_i, a_{i+1}, a_{i+2}$ durch ihr $\operatorname{mex}$. Beachte, dass sich die Länge des Arrays nach Anwendung dieser Operation um $2$ verringert.

Finde die minimale Anzahl an Operationen, die Mayoi ausführen muss, damit das Array in nichtfallender Reihenfolge sortiert ist. Falls dies unmöglich ist, gib $-1$ aus.

Eingabe

Die erste Zeile der Eingabe enthält die ganze Zahl $n$ ($2 \le n \le 5 \cdot 10^5$) — die Länge des Arrays $a$.

Die nächste Zeile enthält $n$ ganze Zahlen $a_i$ ($0 \le a_i \le 10^9$) — die Elemente des Arrays $a$.

Ausgabe

Gib eine einzige Zahl aus — die Antwort auf die Aufgabe.

Beispiele

Beispieleingabe 1

3
4 1 3

Beispielausgabe 1

1

Beispieleingabe 2

9
3 0 2 2 3 0 4 7 8

Beispielausgabe 2

2

Beispieleingabe 3

2
4 3

Beispielausgabe 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.