소가 길을 건너간 이유 8

존(지금까지 우리가 도와 온 존과는 다른 사람이다)의 농장에는 $N$종류의 소가 있다. 각 종은 1번 종, 2번 종, ..., $N$번 종이다($1 \le N \le 1000$). $|a-b| \le 4$이면 $a$번 종과 $b$번 종의 소는 서로 친하고, 그렇지 않으면 사이가 나쁘다.

농장에는 곧게 뻗은 길이 하나 있고, 길 양쪽에 목초지가 $N$개씩 있다. 왼쪽의 각 목초지에는 서로 다른 종의 소가 한 종씩 살고, 오른쪽도 마찬가지이다. 존은 교통사고를 막으려고 횡단보도를 설치하려 한다. 각 횡단보도는 왼쪽 목초지 하나와 오른쪽 목초지 하나를 잇고, 길에 수직일 필요는 없다. 횡단보도는 서로 친한 종의 소가 사는 두 목초지만 이을 수 있다. 각 목초지에는 횡단보도가 많아야 하나만 있어야 하고, 두 횡단보도가 서로 교차해서는 안 된다.

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

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

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