Universal Cup Judging System

Universal Cup

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

$\operatorname{mex}(S)$를 집합 $S$에 포함되지 않은 가장 작은 음이 아닌 정수로 정의합시다.

하치쿠지 마요이(Mayoi Hachikuji)는 $n$개의 원소로 이루어진 배열 $a$를 가지고 있으며, 이 배열이 비내림차순으로 정렬되기를 원합니다. 이를 위해 그녀는 다음 연산을 원하는 만큼(0번 가능) 수행할 수 있습니다:

  • 정수 $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

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.