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 hai bài trước. Giờ đây ông nhận ra rằng ngưỡng xác định sự thân thiện tinh tế hơn đôi chút so với suy nghĩ trước đây: hai giống \(a\) và \(b\) thân thiện nếu \(|a-b| \leq K\), ngược lại thì không thân thiện.

Cho trước thứ tự các cánh đồng ở hai phía con đường chạy qua trang trại của FJ, hãy đếm số cặp giống không thân thiện và giao nhau, trong đó một cặp giống giao nhau được định nghĩa như trong các bài trước.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) (\(1 \leq N \leq 100,000\)) và \(K\) (\(0 \leq K < 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ố cặp giống không thân thiện và giao nhau.

Ví dụ

4 1
4
3
2
1
1
4
2
3

2

Nguồn

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

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