소가 길을 건너간 이유 11

존의 고민을 해결할 방법을 찾아 알려 주러 가던 우리는 길을 잃고 말았다. 도착한 곳도 존의 농장이긴 했지만, 목초지 $2N$개는 없고 웬 $N \times N$ 격자가 있었다. 알고 보니 동명이인의 농장이었다. 그 사이에 우리가 도와주려던 존은 자기 코드를 아무리 디버깅해도 틀렸다는 판정이나 런타임 에러가 나자 포기하고 두 번째 방안을 시도하고 있다.

존은 최근에 일부 종끼리 친하다는 사실을 알게 되었다. 존의 농장에는 1번 종, 2번 종, ..., $N$번 종까지 $N$ 종류의 소가 있다. $|a-b| \le 4$이면 $a$번 종과 $b$번 종의 소는 친하고, 그렇지 않으면 사이가 나쁘다.

존 도와주기 협회에 새로 가입한 사람들을 위해 농장의 구조를 다시 설명한다. 농장에는 곧은 길이 하나 있고, 길 양쪽에 목초지가 $N$개씩 있다. 왼쪽 목초지에는 각 종의 소가 한 목초지씩 차지하고 있고, 오른쪽도 마찬가지이다. 존은 교통사고를 막으려고 횡단보도를 설치하려 한다. 각 횡단보도는 왼쪽 목초지 하나와 오른쪽 목초지 하나를 이어야 하며, 길에 수직일 필요는 없다. 물론 사이가 좋은 소끼리만 연결해야 한다. 각 목초지에는 횡단보도가 최대 한 개만 있어야 하고, 횡단보도끼리 서로 교차하면 안 된다.

조건을 지키면서 횡단보도를 최대한 많이 설치하도록 존을 도와주자.

첫째 줄에 $N$ ($1 \le N \le 100\,000$)이 주어진다. 다음 $N$개의 줄에는 길 왼쪽의 목초지에 있는 소의 종 번호가 순서대로 한 줄에 하나씩 주어진다. 각 종은 정확히 한 번씩 나타난다. 그다음 $N$개의 줄에는 길 오른쪽의 목초지가 같은 방식으로 주어진다.

조건을 만족하도록 설치할 수 있는 횡단보도의 최대 개수를 출력한다.