Hay $N$ estudiantes en una clase. A cada estudiante se le asigna un número del $0$ al $N - 1$ de acuerdo con su clasificación actual en la clase. Es decir, el estudiante $i$ (para todo $0 \le i \le N - 1$) tiene actualmente el rango $i$. Aquí, el rango $0$ es el mejor, mientras que el rango $N-1$ es el peor.

Recientemente se llevaron a cabo exámenes de inglés y matemáticas. El estudiante $i$ (para todo $0 \le i \le N - 1$) obtuvo el rango $A[i]$ en inglés y $B[i]$ en matemáticas. $A$ y $B$ son permutaciones de longitud $N$.

¿Qué es una permutación de longitud $N$? En este problema, una permutación $P$ de longitud $N$ es un arreglo de longitud $N$ tal que $0 \leq P[i] \leq N-1$ para todo $0 \leq i \leq N-1$ y $P[i] \neq P[j]$ para todo $0 \leq i < j \leq N-1$. Por ejemplo, $[2,1,0]$ es una permutación de longitud $3$, pero $[1,2,3]$ y $[2,0,2]$ no son permutaciones de longitud $3$.

El profesor desea reclasificar a los estudiantes. El nuevo rango puede representarse mediante una permutación $P$.

Para cada estudiante $i$, el nuevo rango en la clase debe satisfacer al menos una de las siguientes condiciones:

• Para todo $j$ tal que $P[j] < P[i]$, el estudiante $j$ es mejor que el estudiante $i$ en inglés ($A[j] < A[i]$), O
• Para todo $j$ tal que $P[j] < P[i]$, el estudiante $j$ es mejor que el estudiante $i$ en matemáticas ($B[j] < B[i]$).

Advertencia: La condición solo se aplica a los $j$ tales que $P[j] < P[i]$. No hay restricciones para aquellos $j$ tales que $P[j] \geq P[i]$. Para cada estudiante $i$, al evaluar si se cumple la condición, primero deben elegir una materia y evaluar dicha materia frente a los estudiantes $j$. La materia en la que $j$ es mejor que el estudiante $i$ debe ser la misma para diferentes $j$, dado el mismo $i$. No se puede cambiar de materia mientras se evalúa la condición para el estudiante $i$.

La insatisfacción del nuevo rango de la clase se define como la mayor caída en el rango entre todos los estudiantes. En otras palabras, la insatisfacción es el valor máximo de $P[i] - i$ (para todo $0 \leq i \leq N - 1$).

Advertencia: La insatisfacción es el valor máximo de $P[i] - i$; los valores de $i - P[i]$ no afectan la insatisfacción.

Encuentre la mínima insatisfacción posible del nuevo rango de la clase.

Detalles de implementación

Debe implementar el siguiente procedimiento:

int minimum_dissatisfaction(int N, std::vector<int> A, std::vector<int> B)

• $N$: el número de estudiantes.
• $A$: un arreglo de longitud $N$ que describe el rango del examen de inglés.
• $B$: un arreglo de longitud $N$ que describe el rango del examen de matemáticas.
• Este procedimiento debe devolver la insatisfacción mínima del nuevo rango de la clase.
• Este procedimiento se llama exactamente una vez.

Restricciones

• $1 \leq N \leq 5\;000\;000$.
• $0 \leq A[i], B[i] \leq N - 1$, para todo $0 \leq i \leq N - 1$.
• $A[i] \neq A[j]$, para todo $0 \leq i < j \leq N - 1$.
• $B[i] \neq B[j]$, para todo $0 \leq i < j \leq N - 1$.

Subtareas

1. (3 puntos) $N \leq 8$.
2. (4 puntos) $N \leq 20$.
3. (13 puntos) $N \leq 500$.
4. (12 puntos) $N \leq 3000$, $A[i] + B[i] = N - 1$ para todo $0 \leq i \leq N - 1$.
5. (19 puntos) $N \leq 3000$.
6. (15 puntos) $N \leq 100\;000, A[i] + B[i] = N - 1$ para todo $0 \leq i \leq N - 1$.
7. (17 puntos) $N \leq 100\;000$.
8. (17 puntos) Sin restricciones adicionales.

Nota: para la subtarea 8, el evaluador por sí solo garantiza consumir 1500ms de los 3000ms del límite de tiempo.

Ejemplos

Considere la siguiente llamada:

minimum_dissatisfaction(5, [3, 0, 4, 1, 2], [0, 3, 2, 4, 1])

En este ejemplo, una forma de asignar el nuevo rango es $P = [0, 2, 3, 4, 1]$.

Considere al estudiante $1$ con $P[1] = 2$. Todos los estudiantes $j$ con $P[j] < P[1]$ tienen un mejor rango en matemáticas que el estudiante $1$, por lo que este estudiante satisface la condición de rango de la clase.

A continuación, considere al estudiante $2$ con $P[2] = 3$. Todos los estudiantes $j$ con $P[j] < P[2]$ tienen un mejor rango en inglés que el estudiante $2$, por lo que este estudiante también satisface la condición de rango de la clase.

Se puede verificar para todos los demás estudiantes que también cumplen la condición de rango de la clase.

La insatisfacción del nuevo rango es $1$. No existe otro nuevo rango con menor insatisfacción, por lo que el procedimiento debe devolver $1$.

Evaluador de muestra

Formato de entrada:

N
A[0] A[1] ... A[N - 1]
B[0] B[1] ... B[N - 1]

Formato de salida:

Un entero que representa el valor de retorno de minimum_dissatisfaction.