Farmer John nuôi \(N\) giống bò (\(1 \leq N \leq 1000\)), được đánh số thuận tiện từ \(1 \ldots N\). Một số cặp giống thân thiện với nhau hơn những cặp khác, và tính chất này có thể được mô tả dễ dàng theo mã số giống: hai giống \(a\) và \(b\) thân thiện nếu \(|a-b| \leq 4\), ngược lại thì không thân thiện.

Một con đường dài chạy qua trang trại của FJ. Có một dãy \(N\) cánh đồng ở một phía của con đường (mỗi giống được dành riêng một cánh đồng), và một dãy \(N\) cánh đồng ở phía bên kia (cũng mỗi giống một cánh đồng). Để giúp đàn bò băng qua đường an toàn, FJ muốn kẻ các vạch qua đường. Mỗi vạch qua đường phải nối một cánh đồng ở phía này với một cánh đồng ở phía kia sao cho mã số giống của hai cánh đồng là thân thiện (bò có thể đi vào cánh đồng dành cho giống khác, miễn là hai giống thân thiện). Mỗi cánh đồng chỉ có thể tiếp cận được qua nhiều nhất một vạch qua đường (do đó các vạch qua đường không gặp nhau tại đầu mút).

Cho trước thứ tự của \(N\) cánh đồng ở hai phía con đường chạy qua trang trại của FJ, hãy giúp FJ xác định số vạch qua đường lớn nhất có thể kẻ sao cho không có hai vạch nào giao nhau.

Dữ liệu vào

Dòng đầu tiên chứa \(N\). \(N\) dòng tiếp theo mô tả thứ tự các cánh đồng ở một phía của con đường theo mã số giống; mỗi mã số giống là một số nguyên trong khoảng \(1 \ldots N\). \(N\) dòng cuối cùng mô tả thứ tự các cánh đồng ở phía bên kia của con đường theo mã số giống. Mỗi mã số giống xuất hiện đúng một lần trong mỗi thứ tự.

Dữ liệu ra

In ra số "vạch qua đường thân thiện" đôi một không giao nhau lớn nhất mà Farmer John có thể kẻ qua con đường.

Ví dụ

6
1
2
3
4
5
6
6
5
4
3
2
1

5

Nguồn

USACO 2017 February Contest, Gold — Why Did the Cow Cross the Road II. Tác giả đề: Brian Dean.

https://usaco.org/index.php?page=viewproblem2&cpid=718