한 반에 $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$인 순열이란 무엇인가? 이 문제에서 길이가 $N$인 순열 $P$는 모든 $0 \leq i \leq N-1$에 대해 $0 \leq P[i] \leq N-1$을 만족하고, 모든 $0 \leq i < j \leq N-1$에 대해 $P[i] \neq P[j]$를 만족하는 길이 $N$의 배열이다. 예를 들어, $[2,1,0]$은 길이가 $3$인 순열이지만, $[1,2,3]$과 $[2,0,2]$는 길이가 $3$인 순열이 아니다.

교사는 학생들의 등수를 다시 매기고자 한다. 새로운 등수는 순열 $P$로 나타낼 수 있다.

각 학생 $i$에 대해, 새로운 학급 등수는 다음 조건 중 적어도 하나를 만족해야 한다.

• $P[j] < P[i]$인 모든 $j$에 대하여, 학생 $j$가 학생 $i$보다 영어 성적이 좋다($A[j] < A[i]$). 또는
• $P[j] < P[i]$인 모든 $j$에 대하여, 학생 $j$가 학생 $i$보다 수학 성적이 좋다($B[j] < B[i]$).

주의: 이 조건은 $P[j] < P[i]$인 $j$에 대해서만 적용된다. $P[j] \geq P[i]$인 $j$에 대해서는 제약이 없다. 각 학생 $i$는 조건을 만족하는지 평가할 때, 먼저 과목 하나를 선택하여 해당 과목을 다른 학생 $j$들과 비교해야 한다. 학생 $i$에 대해 조건을 평가할 때, $j$가 학생 $i$보다 성적이 좋은 과목은 모든 $j$에 대해 동일해야 한다. 학생 $i$에 대한 조건을 평가하는 도중에 과목을 바꿀 수 없다.

새로운 학급 등수의 불만족도는 모든 학생 중 가장 큰 등수 하락폭으로 정의된다. 즉, 불만족도는 모든 $0 \leq i \leq N - 1$에 대한 $P[i] - i$의 최댓값이다.

주의: 불만족도는 $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 i \leq N - 1$에 대해 $0 \leq A[i], B[i] \leq N - 1$.
• 모든 $0 \leq i < j \leq N - 1$에 대해 $A[i] \neq A[j]$.
• 모든 $0 \leq i < j \leq N - 1$에 대해 $B[i] \neq B[j]$.

서브태스크

1. (3점) $N \leq 8$.
2. (4점) $N \leq 20$.
3. (13점) $N \leq 500$.
4. (12점) $N \leq 3000$, 모든 $0 \leq i \leq N - 1$에 대해 $A[i] + B[i] = N - 1$.
5. (19점) $N \leq 3000$.
6. (15점) $N \leq 100\;000$, 모든 $0 \leq i \leq N - 1$에 대해 $A[i] + B[i] = N - 1$.
7. (17점) $N \leq 100\;000$.
8. (17점) 추가 제약 없음.

참고: 서브태스크 8의 경우, 채점기 자체만으로도 3000ms의 시간 제한 중 1500ms를 소모할 수 있다.

예제

다음 호출을 고려하자.

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

이 예제에서 새로운 등수를 할당하는 한 가지 방법은 $P = [0, 2, 3, 4, 1]$이다.

$P[1] = 2$인 학생 $1$을 고려하자. $P[j] < P[1]$인 모든 학생 $j$는 학생 $1$보다 수학 등수가 높으므로, 이 학생은 학급 등수 조건을 만족한다.

다음으로 $P[2] = 3$인 학생 $2$를 고려하자. $P[j] < P[2]$인 모든 학생 $j$는 학생 $2$보다 영어 등수가 높으므로, 이 학생 또한 학급 등수 조건을 만족한다.

다른 모든 학생들도 학급 등수 조건을 만족함을 확인할 수 있다.

새로운 등수의 불만족도는 $1$이다. 불만족도가 더 낮은 다른 새로운 등수는 없으므로, 이 프로시저는 $1$을 반환해야 한다.

예제 입력

입력 형식:

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

출력 형식:

minimum_dissatisfaction의 반환 값을 나타내는 정수.