W klasie jest $N$ uczniów. Każdemu uczniowi przypisano numer od $0$ do $N - 1$ zgodnie z jego obecnym rankingiem w klasie. Oznacza to, że uczeń $i$ (dla wszystkich $0 \le i \le N - 1$) ma obecnie rangę $i$. Ranga $0$ jest najlepsza, a ranga $N-1$ najgorsza.

Niedawno odbyły się egzaminy z języka angielskiego i matematyki. Uczeń $i$ (dla wszystkich $0 \le i \le N - 1$) zajął miejsce $A[i]$ z angielskiego oraz $B[i]$ z matematyki. $A$ oraz $B$ są permutacjami długości $N$.

Czym jest permutacja długości $N$? W tym zadaniu permutacja $P$ długości $N$ to tablica długości $N$, taka że $0 \leq P[i] \leq N-1$ dla wszystkich $0 \leq i \leq N-1$ oraz $P[i] \neq P[j]$ dla wszystkich $0 \leq i < j \leq N-1$. Na przykład $[2,1,0]$ jest permutacją długości $3$, ale $[1,2,3]$ oraz $[2,0,2]$ nie są permutacjami długości $3$.

Nauczyciel chciałby przydzielić uczniom nowe rangi. Nowy ranking można przedstawić za pomocą permutacji $P$.

Dla każdego ucznia $i$, nowy ranking w klasie musi spełniać co najmniej jeden z poniższych warunków:

• Dla wszystkich $j$ takich, że $P[j] < P[i]$, uczeń $j$ jest lepszy od ucznia $i$ z języka angielskiego ($A[j] < A[i]$), LUB
• Dla wszystkich $j$ takich, że $P[j] < P[i]$, uczeń $j$ jest lepszy od ucznia $i$ z matematyki ($B[j] < B[i]$).

Ostrzeżenie: Warunek dotyczy tylko tych $j$, dla których $P[j] < P[i]$. Nie ma ograniczeń dla tych $j$, dla których $P[j] \geq P[i]$. Dla każdego ucznia $i$, oceniając czy warunek jest spełniony, musi on najpierw wybrać przedmiot i ocenić ten przedmiot w odniesieniu do uczniów $j$. Przedmiot, w którym $j$ jest lepszy od ucznia $i$, musi być taki sam dla różnych $j$, przy ustalonym $i$. Nie można zmieniać przedmiotu podczas sprawdzania warunku dla ucznia $i$.

Niezadowolenie z nowego rankingu definiuje się jako największy spadek w rankingu wśród wszystkich uczniów. Innymi słowy, niezadowolenie to maksymalna wartość $P[i] - i$ (dla wszystkich $0 \leq i \leq N - 1$).

Ostrzeżenie: Niezadowolenie to maksymalna wartość $P[i] - i$, wartości $i - P[i]$ nie wpływają na niezadowolenie.

Znajdź minimalne możliwe niezadowolenie nowego rankingu.

Szczegóły implementacji

Należy zaimplementować następującą procedurę:

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

• $N$: liczba uczniów.
• $A$: tablica długości $N$ opisująca ranking z egzaminu z języka angielskiego.
• $B$: tablica długości $N$ opisująca ranking z egzaminu z matematyki.
• Procedura powinna zwrócić minimalne niezadowolenie nowego rankingu.
• Procedura jest wywoływana dokładnie raz.

Ograniczenia

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

Podzadania

1. (3 punkty) $N \leq 8$.
2. (4 punkty) $N \leq 20$.
3. (13 punktów) $N \leq 500$.
4. (12 punktów) $N \leq 3000$, $A[i] + B[i] = N - 1$ dla wszystkich $0 \leq i \leq N - 1$.
5. (19 punktów) $N \leq 3000$.
6. (15 punktów) $N \leq 100\,000, A[i] + B[i] = N - 1$ dla wszystkich $0 \leq i \leq N - 1$.
7. (17 punktów) $N \leq 100\,000$.
8. (17 punktów) Brak dodatkowych ograniczeń.

Uwaga: dla podzadania 8, sam grader zużywa 1500 ms z limitu czasu 3000 ms.

Przykład

Rozważmy następujące wywołanie:

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

W tym przykładzie jednym ze sposobów przypisania nowego rankingu jest $P = [0, 2, 3, 4, 1]$.

Rozważmy ucznia $1$, dla którego $P[1] = 2$. Wszyscy uczniowie $j$, dla których $P[j] < P[1]$, mają lepszą rangę z matematyki niż uczeń $1$, więc ten uczeń spełnia warunek rankingu.

Następnie rozważmy ucznia $2$, dla którego $P[2] = 3$. Wszyscy uczniowie $j$, dla których $P[j] < P[2]$, mają lepszą rangę z angielskiego niż uczeń $2$, więc ten uczeń również spełnia warunek rankingu.

Można sprawdzić, że wszyscy pozostali uczniowie również spełniają warunek rankingu.

Niezadowolenie nowego rankingu wynosi $1$. Nie ma innego nowego rankingu z mniejszym niezadowoleniem, więc procedura powinna zwrócić $1$.

Przykład użycia

Format wejścia:

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

Format wyjścia:

Liczba całkowita reprezentująca wartość zwróconą przez minimum_dissatisfaction.