Universal Cup Judging System

Universal Cup

時間限制: 1.5 s 記憶體限制: 512 MB 總分: 100 可 Hack ✓
统计

Låt oss definiera $\operatorname{mex}(S)$ som det minsta icke-negativa heltalet som inte ingår i $S$.

Mayoi Hachikuji har en array $a$ bestående av $n$ element som hon vill ska vara sorterad i icke-avtagande ordning. För att göra detta kan hon utföra följande operation valfritt antal gånger (möjligen noll):

  • Välj ett heltal $i \in [1, \operatorname{length}(a) - 2]$ och ersätt $a_i, a_{i+1}, a_{i+2}$ med deras $\operatorname{mex}$. Observera att efter att denna operation har utförts minskar arrayens längd med $2$.

Hitta det minsta antalet operationer Mayoi behöver utföra för att göra arrayen sorterad i icke-avtagande ordning. Om det är omöjligt att göra detta, skriv ut $-1$.

Indata

Den första raden i indatan innehåller heltalet $n$ ($2 \le n \le 5 \cdot 10^5$) — längden på arrayen $a$.

Nästa rad innehåller $n$ heltal $a_i$ ($0 \le a_i \le 10^9$) — elementen i arrayen $a$.

Utdata

Skriv ut ett tal — svaret på problemet.

Exempel

Exempelindata 1

3
4 1 3

Exempelutdata 1

1

Exempelindata 2

9
3 0 2 2 3 0 4 7 8

Exempelutdata 2

2

Exempelindata 3

2
4 3

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