35052번 - 끝내주는 분할

문제

두 개의 순열을 가지고 무언가 생각하던 snrnsidy는 아래와 같은 문제를 만들어 냈다.

길이가 $N$인 두 순열 $A$와 $B$가 주어진다. $A$와 $B$에서 동일한 위치를 골라서 각각을 $K$개의 연속된 조각으로 나누려고 한다. 단, 각 $i = 1, 2, \dots, K$와 $j_i= 1, 2, \dots, (i$번째 조각의 길이$)$에 대해, $A$의 $i$번째 조각의 $j_i$번째 최솟값의 위치와 $B$의 $i$번째 조각의 $j_i$번째 최솟값의 위치가 서로 모두 같아야 한다.

예를 들어, $A =(1, 3, 2, 5, 4)$이고 $B = (5, 4, 3, 2, 1)$라 하자. 만약 $A$를 $(1), (3, 2), (5, 4)$로 나누면, $B$는 $(5), (4, 3), (2, 1)$로 나누어지며, 위에서 설명한 조건을 만족시킨다. 물론 $A$와 $B$를 길이가 1ドル$인 $n$개의 조각들로 나누면 위 조건을 쉽게 만족시킬 수 있다.

따라서 우리는 조건을 만족하면서 조각의 수 $K$가 최소가 되도록 나누고자 하며, 이러한 분할을 끝내주는 분할이라고 하자. 위 예시에서 $K = 3$인 분할이 끝내주는 분할이다.

하지만 snrnsidy는 끝내주는 분할을 찾는 프로그램을 구현할 생각에 눈앞이 캄캄해졌다.

하아...

한숨을 쉬는 snrnsidy를 대신해 여러분이 끝내주는 분할을 찾는 프로그램을 구현해 주자.

입력

첫째 줄에 순열 $A$와 $B$의 길이를 나타내는 양의 정수 $N$이 주어진다. $(1 \le N \le 300,000円)$

둘째 줄에 순열 $A$의 원소 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다.

셋째 줄에 순열 $B$의 원소 $B_1, B_2, \cdots, B_N$이 공백으로 구분되어 주어진다.

출력

첫째 줄에 끝내주는 분할의 조각 수를 출력한다.

제한

노트

길이가 $N$인 순열이란 순열의 원소로 1ドル$부터 $N$까지의 정수가 모두 빠짐없이 단 한 번씩 나오는 수열을 의미한다. 즉, 순열 $A = \left(A_1, A_2 , \cdots, A_N\right)$는 아래 조건을 만족한다.

• $A_i$는 1ドル$ 이상 $N$ 이하의 정수
• $i \neq j$이면 $A_i \neq A_j$