전당포

전당포를 운영하고 있다. 가게 창가에 물건을 진열해서 길가에서 보이게 한다. 같은 종류의 물건을 여러 번 진열하기도 한다. 간단히 생각하기 위해 진열된 물건을 값의 수열로 본다. 각 값은 진열된 물건의 종류를 나타낸다.

예를 들어 진열대가 다음 수열이라고 하자.

$1, 2, 6, 2, 7, 9, 8, 5$

최근 휴가에서 돌아와 보니 직원이 물건을 옮겨서 진열을 완전히 바꿔 놓았다. 위의 진열대는 다음과 같이 바뀌어 있었다.

$2, 6, 1, 2, 9, 7, 5, 8$

이런 모습은 손님을 헷갈리게 하고 단골을 놓칠 수 있다. 하지만 물건을 원래 자리로 되돌릴 시간이 없다.

그래서 타협안으로, 창가에 칸막이를 세워 진열된 물건을 연속된 묶음으로 나누기로 했다. 각 묶음은 원래 원하던 배치에서 그 자리에 있던 물건 종류들을 다시 늘어놓은 것이어야 한다.

더 정확히 말하면, $a_1, \ldots, a_N$을 첫 번째 수열, $b_1, \ldots, b_N$을 두 번째 수열이라고 하자. $b_i, b_{i+1}, \ldots, b_j$가 $a_i, a_{i+1}, \ldots, a_j$를 재배열한 것이면 $i, i+1, \ldots, j$ 주변에 칸막이를 놓을 수 있다. 수열의 처음이나 끝에 칸막이를 놓을 필요는 없다. $a_i = b_i$이면 인덱스 $i$ 하나만으로도 묶음을 만들 수 있다.

위 수열에서는 다음 세 위치에 칸막이 #를 놓을 수 있다.

2 6 1 # 2 # 7 9 # 5 8

이 성질을 가진 묶음을 네 개보다 많이 나눌 수는 없다.

두 수열이 주어졌을 때, 새 수열을 가장 많은 묶음으로 나누는 방법을 구하라.

첫 줄에 두 수열의 길이를 나타내는 정수 $N$ ($1 \leq N \leq 300\,000$)이 주어진다.

다음 줄에는 원래 수열 $a_1, \ldots, a_N$ ($1 \leq a_i \leq 10^9$)이 정수 $N$개로 주어진다.

다음 줄에는 재배열된 수열 $b_1, \ldots, b_N$ ($1 \leq b_i \leq 10^9$)이 정수 $N$개로 주어진다. 값 $b_1, \ldots, b_N$은 값 $a_1, \ldots, a_N$을 재배열한 것이다.

재배열된 수열을 칸막이 (#)로 나누어 출력하라. 나눈 결과는 유효해야 하며, 묶음의 수가 최대여야 한다.

해가 여러 개라면 그중 어느 것을 출력해도 된다.