Bartek es un conocido productor de música techno y actualmente está perfeccionando su próximo éxito. Ha creado una pista que consta de $n$ pulsos (beats), numerados consecutivamente del $1$ al $n$. Después de pasar horas en un programa de edición de música, estaba a punto de exportar el archivo mp3, pero notó que los pulsos están dispuestos actualmente en el orden $a_1, a_2, \dots, a_n$. Bartek necesita obtener un orden creciente de los pulsos, es decir, $1, 2, \dots, n$.

El programa permite dos tipos de operaciones:

• Mover el último pulso a cualquier posición, p. ej., $(2, 4, 1, 5, \underline{3}) \to (2, \underline{3}, 4, 1, 5)$.
• Mover cualquier pulso al principio, p. ej., $(2, 4, 1, \underline{5}, 3) \to (\underline{5}, 2, 4, 1, 3)$.

¿Cuál es el número mínimo de operaciones necesarias para ordenar los pulsos en orden creciente?

Entrada

La primera línea contiene un entero $n$ ($1 \le n \le 200\,000$), que denota el número de pulsos.

La segunda línea contiene $n$ enteros distintos dos a dos $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n; a_i \ne a_j$), que representan el orden actual de los pulsos en el programa.

Salida

Imprime un solo entero: el número mínimo de operaciones requeridas.

Ejemplos

Entrada 1

6
3 2 5 4 1 6

Salida 1

4

Entrada 2

9
3 1 2 5 6 4 9 7 8

Salida 2

6

Nota

Comenzamos con la secuencia de pulsos $(3, 2, 5, 4, 1, 6)$. Aquí hay una forma de lograr el orden deseado en cuatro operaciones:

• Mover el último pulso dos lugares a la izquierda: $(3, 2, 5, \underline{6}, 4, 1)$.
• Mover el pulso $2$ al principio: $(\underline{2}, 3, 5, 6, 4, 1)$.
• Mover el pulso $1$ al principio: $(\underline{1}, 2, 3, 5, 6, 4)$.
• Mover el último pulso dos lugares a la izquierda: $(1, 2, 3, \underline{4}, 5, 6)$.

Es posible obtener un orden creciente de otras maneras usando cuatro operaciones, pero no se puede hacer en tres operaciones, por lo que el resultado es $4$.