Farmer John tiếp tục suy ngẫm về vấn đề bò băng qua con đường chạy qua trang trại của mình, đã được giới thiệu trong bài trước. Ông nhận ra rằng sự tương tác giữa một số cặp giống thực ra có thể chấp nhận được nếu chúng thân thiện với nhau, 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. 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.

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 (mỗi phía vẫn có đúng một cánh đồng cho mỗi giống), 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 và mỗi vạch nối một cặp cánh đồng dành cho 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).

Dữ liệu vào

Dòng đầu tiên chứa \(N\) (\(1 \leq N \leq 100,000\)). \(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, Platinum — Why Did the Cow Cross the Road II. Tác giả đề: Brian Dean.

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