Il y a $N$ élèves dans une classe. Chaque élève se voit attribuer un numéro de $0$ à $N - 1$ selon son classement actuel. C'est-à-dire que l'élève $i$ (pour tout $0 \le i \le N - 1$) a actuellement le rang $i$. Ici, le rang $0$ est le meilleur tandis que le rang $N-1$ est le pire.

Des examens d'anglais et de mathématiques ont eu lieu récemment. L'élève $i$ (pour tout $0 \le i \le N - 1$) a obtenu le rang $A[i]$ en anglais et $B[i]$ en mathématiques. $A$ et $B$ sont des permutations de longueur $N$.

Qu'est-ce qu'une permutation de longueur $N$ ? Dans ce problème, une permutation $P$ de longueur $N$ est un tableau de longueur $N$ tel que $0 \leq P[i] \leq N-1$ pour tout $0 \leq i \leq N-1$ et $P[i] \neq P[j]$ pour tout $0 \leq i < j \leq N-1$. Par exemple, $[2,1,0]$ est une permutation de longueur $3$, mais $[1,2,3]$ et $[2,0,2]$ ne sont pas des permutations de longueur $3$.

L'enseignant souhaite reclasser les élèves. Le nouveau rang peut être représenté par une permutation $P$.

Pour chaque élève $i$, le nouveau classement doit satisfaire au moins une des conditions suivantes :

• Pour tout $j$ tel que $P[j] < P[i]$, l'élève $j$ est meilleur que l'élève $i$ en anglais ($A[j] < A[i]$), OU
• Pour tout $j$ tel que $P[j] < P[i]$, l'élève $j$ est meilleur que l'élève $i$ en mathématiques ($B[j] < B[i]$).

Avertissement La condition s'applique uniquement aux $j$ tels que $P[j] < P[i]$. Il n'y a aucune contrainte pour les $j$ tels que $P[j] \geq P[i]$. Pour chaque élève $i$, lors de l'évaluation de la satisfaction de la condition, il doit d'abord choisir une matière et évaluer ladite matière par rapport aux élèves $j$. La matière où $j$ est meilleur que l'élève $i$ doit être la même pour différents $j$, pour un même $i$. Vous ne pouvez pas changer de matière lors de l'évaluation de la condition pour l'élève $i$.

L' insatisfaction du nouveau classement est définie comme la plus grande chute de rang parmi tous les élèves. En d'autres termes, l'insatisfaction est la valeur maximale de $P[i] - i$ (pour tout $0 \leq i \leq N - 1$).

Avertissement L'insatisfaction est la valeur maximale de $P[i] - i$, les valeurs de $i - P[i]$ n'affectent pas l'insatisfaction.

Trouvez l'insatisfaction minimale possible du nouveau classement.

Détails d'implémentation

Vous devez implémenter la procédure suivante.

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

• $N$ : le nombre d'élèves.
• $A$ : un tableau de longueur $N$ décrivant le classement de l'examen d'anglais.
• $B$ : un tableau de longueur $N$ décrivant le classement de l'examen de mathématiques.
• Cette procédure doit retourner l'insatisfaction minimale du nouveau classement.
• Cette procédure est appelée exactement une fois.

Contraintes

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

Sous-tâches

1. (3 points) $N \leq 8$.
2. (4 points) $N \leq 20$.
3. (13 points) $N \leq 500$.
4. (12 points) $N \leq 3000$, $A[i] + B[i] = N - 1$ pour tout $0 \leq i \leq N - 1$.
5. (19 points) $N \leq 3000$.
6. (15 points) $N \leq 100\;000, A[i] + B[i] = N - 1$ pour tout $0 \leq i \leq N - 1$.
7. (17 points) $N \leq 100\;000$.
8. (17 points) Aucune contrainte supplémentaire.

Remarque : pour la sous-tâche 8, le correcteur seul est garanti de consommer 1500ms sur la limite de temps de 3000ms.

Exemples

Considérez l'appel suivant.

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

Dans cet exemple, une façon d'attribuer le nouveau classement est $P = [0, 2, 3, 4, 1]$.

Considérez l'élève $1$ avec $P[1] = 2$. Tous les élèves $j$ avec $P[j] < P[1]$ ont un meilleur rang en mathématiques que l'élève $1$, donc cet élève satisfait la condition de classement.

Ensuite, considérez l'élève $2$ avec $P[2] = 3$. Tous les élèves $j$ avec $P[j] < P[2]$ ont un meilleur rang en anglais que l'élève $2$, donc cet élève satisfait également la condition de classement.

On peut vérifier pour tous les autres élèves qu'ils satisfont également la condition de classement.

L'insatisfaction du nouveau classement est $1$. Il n'existe aucun autre nouveau classement avec une insatisfaction plus faible, donc la procédure doit retourner $1$.

Correcteur d'exemple

Format d'entrée :

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

Format de sortie :

Un entier représentant la valeur de retour de minimum_dissatisfaction.