Universal Cup Judging System

Universal Cup

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

Definamos $\operatorname{mex}(S)$ como el menor entero no negativo que no está contenido en $S$.

Mayoi Hachikuji tiene un arreglo $a$ que consta de $n$ elementos y quiere que quede ordenado en orden no decreciente. Para lograrlo, puede realizar la siguiente operación cualquier número de veces (posiblemente cero):

  • Elegir un entero $i \in [1, \operatorname{length}(a) - 2]$ y reemplazar $a_i, a_{i+1}, a_{i+2}$ por su $\operatorname{mex}$. Observa que después de aplicar esta operación, la longitud del arreglo disminuye en $2$.

Encuentra el número mínimo de operaciones que Mayoi necesita realizar para que el arreglo quede ordenado en orden no decreciente. En caso de que sea imposible lograrlo, imprime $-1$.

Entrada

La primera línea de la entrada contiene el entero $n$ ($2 \le n \le 5 \cdot 10^5$) — la longitud del arreglo $a$.

La siguiente línea contiene $n$ enteros $a_i$ ($0 \le a_i \le 10^9$) — los elementos del arreglo $a$.

Salida

Imprime un único número — la respuesta al problema.

Ejemplos

Entrada de ejemplo 1

3
4 1 3

Salida de ejemplo 1

1

Entrada de ejemplo 2

9
3 0 2 2 3 0 4 7 8

Salida de ejemplo 2

2

Entrada de ejemplo 3

2
4 3

Salida de ejemplo 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.