В классе $N$ учеников. Каждому ученику присвоен номер от $0$ до $N - 1$ в соответствии с его текущим рейтингом в классе. То есть ученик $i$ (для всех $0 \le i \le N - 1$) в настоящее время имеет рейтинг $i$. Здесь рейтинг $0$ — лучший, а рейтинг $N-1$ — худший.

Недавно были проведены экзамены по английскому языку и математике. Ученик $i$ (для всех $0 \le i \le N - 1$) занял место $A[i]$ по английскому языку и $B[i]$ по математике. $A$ и $B$ являются перестановками длины $N$.

Что такое перестановка длины $N$? В этой задаче перестановка $P$ длины $N$ — это массив длины $N$, такой что $0 \leq P[i] \leq N-1$ для всех $0 \leq i \leq N-1$ и $P[i] \neq P[j]$ для всех $0 \leq i < j \leq N-1$. Например, $[2,1,0]$ является перестановкой длины $3$, а $[1,2,3]$ и $[2,0,2]$ не являются перестановками длины $3$.

Учитель хочет перераспределить рейтинги учеников. Новый рейтинг может быть представлен перестановкой $P$.

Для каждого ученика $i$ новый рейтинг в классе должен удовлетворять хотя бы одному из следующих условий:

• Для всех $j$, таких что $P[j] < P[i]$, ученик $j$ лучше ученика $i$ по английскому языку ($A[j] < A[i]$), ИЛИ
• Для всех $j$, таких что $P[j] < P[i]$, ученик $j$ лучше ученика $i$ по математике ($B[j] < B[i]$).

Предупреждение: Условие применяется только к тем $j$, для которых $P[j] < P[i]$. Для тех $j$, для которых $P[j] \geq P[i]$, ограничений нет. При оценке того, выполняется ли условие для ученика $i$, он должен сначала выбрать предмет и оценить этот предмет по отношению к ученикам $j$. Предмет, по которому $j$ лучше ученика $i$, должен быть одним и тем же для разных $j$ при фиксированном $i$. Вы не можете менять предмет во время проверки условия для одного ученика $i$.

Неудовлетворенность нового рейтинга определяется как наибольшее падение в рейтинге среди всех учеников. Другими словами, неудовлетворенность — это максимальное значение $P[i] - i$ (для всех $0 \leq i \leq N - 1$).

Предупреждение: Неудовлетворенность — это максимальное значение $P[i] - i$, значения $i - P[i]$ не влияют на неудовлетворенность.

Найдите минимально возможную неудовлетворенность нового рейтинга.

Детали реализации

Вам необходимо реализовать следующую функцию:

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

• $N$: количество учеников.
• $A$: массив длины $N$, описывающий рейтинг по английскому языку.
• $B$: массив длины $N$, описывающий рейтинг по математике.
• Функция должна возвращать минимальную неудовлетворенность нового рейтинга.
• Функция вызывается ровно один раз.

Ограничения

• $1 \leq N \leq 5\;000\;000$.
• $0 \leq A[i], B[i] \leq N - 1$, для всех $0 \leq i \leq N - 1$.
• $A[i] \neq A[j]$, для всех $0 \leq i < j \leq N - 1$.
• $B[i] \neq B[j]$, для всех $0 \leq i < j \leq N - 1$.

Подзадачи

1. (3 балла) $N \leq 8$.
2. (4 балла) $N \leq 20$.
3. (13 баллов) $N \leq 500$.
4. (12 баллов) $N \leq 3000$, $A[i] + B[i] = N - 1$ для всех $0 \leq i \leq N - 1$.
5. (19 баллов) $N \leq 3000$.
6. (15 баллов) $N \leq 100\;000, A[i] + B[i] = N - 1$ для всех $0 \leq i \leq N - 1$.
7. (17 баллов) $N \leq 100\;000$.
8. (17 баллов) Без дополнительных ограничений.

Примечание: для подзадачи 8 гарантируется, что только проверяющая система потребляет 1500 мс из 3000 мс лимита времени.

Примеры

Рассмотрим следующий вызов:

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

В этом примере один из способов назначения нового рейтинга — $P = [0, 2, 3, 4, 1]$.

Рассмотрим ученика $1$ с $P[1] = 2$. Все ученики $j$, у которых $P[j] < P[1]$, имеют лучший рейтинг по математике, чем ученик $1$, поэтому этот ученик удовлетворяет условию рейтинга.

Далее рассмотрим ученика $2$ с $P[2] = 3$. Все ученики $j$, у которых $P[j] < P[2]$, имеют лучший рейтинг по английскому языку, чем ученик $2$, поэтому этот ученик также удовлетворяет условию рейтинга.

Можно проверить, что все остальные ученики также удовлетворяют условию рейтинга.

Неудовлетворенность нового рейтинга равна $1$. Не существует другого рейтинга с меньшей неудовлетворенностью, поэтому функция должна вернуть $1$.

Примеры входных и выходных данных

Входные данные 1

5
3 0 4 1 2
0 3 2 4 1

Выходные данные 1

1