시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 30 15 13 76.471%

문제

이번에는 우리가 존의 농장을 제대로 찾아가긴 했는데, 다른 이유로 계획이 실행되지 못했다. 그의 소 친밀도 이론에 오류가 발견되었기 때문이다.

존의 농장에는 N 종류의 소가 있다. 각각 1번 종, 2번 종, ..., N번 종이다. 만약 |a−b| ≤ K라면 a번 종과 b번 종의 소는 친하지만, 그렇지 않으면 사이가 나쁘다. 종별로 목초지 구조가 너무 달라서 한 목초지에는 정해진 종의 소만 방목할 수 있다. i번 목초지에는 i번 소만 방목할 수 있는 것이다. 소가 길을 건널 때는 자신의 종을 방목하는 반대편의 목초지로 이동하는 것이다.

존 도와주기 협회에 새로 가입한 사람들을 위해 농장의 구조를 다시 설명할 것이다. 농장에는 일자형 길이 있고, 양쪽에 목초지가 N개씩 있다. 왼쪽 목초지에는 각 종류의 소가 한 목초지씩 차지하고 있고, 오른쪽도 마찬가지이다. 목초지의 순서가 뒤죽박죽이어서, a종의 소와 b종의 소가 건너는 길이 겹칠 수도 있다. 존이 목초지 건설에 주의를 기울이지 않은 탓이다. 이때 (a,b)를 "가로지르는 쌍"이라고 하자.

이번에는 횡단보도를 설치하기 전에, 사이가 안 좋으면서 가로지르는 쌍이 몇 개인지 세고 싶다. 존 도와주기 협회장의 임기가 다 끝나가기 때문에 이것이 우리에게 주어진 마지막 임무이다. 마지막으로 존을 도와주자.

입력

첫 줄에 N (1 ≤ N ≤ 100,000)과 K (0 ≤ K < N)가 주어진다. 다음 N줄에는 길의 왼쪽에 있는 목초지 번호가 차례대로 주어진다. 각 종은 한 번씩 나타난다. 그 다음 N줄에는 길의 오른쪽에 있는 목초지가 같은 방식으로 주어진다.

출력

사이가 안 좋으면서 가로지르는 쌍의 개수를 출력한다.

예제 입력 1

4 1
4
3
2
1
1
4
2
3

예제 출력 1

2

힌트

1과 4, 1과 3이 사이가 안 좋으면서 가로지르는 쌍이다.

W3sicHJvYmxlbV9pZCI6IjE0NDYwIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjMThjXHVhYzAwIFx1YWUzOFx1Yzc0NCBcdWFjNzRcdWIxMDhcdWFjMDQgXHVjNzc0XHVjNzIwIDEyIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM3NzRcdWJjODhcdWM1ZDBcdWIyOTQgXHVjNmIwXHViOWFjXHVhYzAwPGEgaHJlZj1cImh0dHBzOlwvXC93d3cuYWNtaWNwYy5uZXRcL3Byb2JsZW1cLzE0NDU5XCI+IFx1Yzg3NFx1Yzc1OCBcdWIxOGRcdWM3YTU8XC9hPlx1Yzc0NCBcdWM4MWNcdWIzMDBcdWI4NWMgXHVjYzNlXHVjNTQ0XHVhYzAwXHVhZTM0IFx1ZDU4OFx1YjI5NFx1YjM3MCwgXHViMmU0XHViOTc4IFx1Yzc3NFx1YzcyMFx1Yjg1YyBcdWFjYzRcdWQ2OGRcdWM3NzQgXHVjMmU0XHVkNTg5XHViNDE4XHVjOWMwIFx1YmFiYlx1ZDU4OFx1YjJlNC4gXHVhZGY4XHVjNzU4IFx1YzE4YyBcdWNlNWNcdWJjMDBcdWIzYzQgXHVjNzc0XHViODYwXHVjNWQwIFx1YzYyNFx1Yjk1OFx1YWMwMCBcdWJjMWNcdWFjYWNcdWI0MThcdWM1YzhcdWFlMzAgXHViNTRjXHViYjM4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM4NzRcdWM3NTggXHViMThkXHVjN2E1XHVjNWQwXHViMjk0IE4gXHVjODg1XHViOTU4XHVjNzU4IFx1YzE4Y1x1YWMwMCBcdWM3ODhcdWIyZTQuIFx1YWMwMVx1YWMwMSAxXHViYzg4IFx1Yzg4NSwgMlx1YmM4OCBcdWM4ODUsIC4uLiwgTlx1YmM4OCBcdWM4ODVcdWM3NzRcdWIyZTQuIFx1YjljY1x1YzU3ZCB8YSZtaW51cztifCAmbGU7IEtcdWI3N2NcdWJhNzQgYVx1YmM4OCBcdWM4ODVcdWFjZmMgYlx1YmM4OCBcdWM4ODVcdWM3NTggXHVjMThjXHViMjk0IFx1Y2U1Y1x1ZDU1OFx1YzljMFx1YjljYywgXHVhZGY4XHViODA3XHVjOWMwIFx1YzU0YVx1YzczY1x1YmE3NCBcdWMwYWNcdWM3NzRcdWFjMDAgXHViMDk4XHVjMDU4XHViMmU0LiBcdWM4ODVcdWJjYzRcdWI4NWMgXHViYWE5XHVjZDA4XHVjOWMwIFx1YWQ2Y1x1Yzg3MFx1YWMwMCBcdWIxMDhcdWJiMzQgXHViMmVjXHViNzdjXHVjMTFjIFx1ZDU1YyBcdWJhYTlcdWNkMDhcdWM5YzBcdWM1ZDBcdWIyOTQgXHVjODE1XHVkNTc0XHVjOWM0IFx1Yzg4NVx1Yzc1OCBcdWMxOGNcdWI5Y2MgXHViYzI5XHViYWE5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIGlcdWJjODggXHViYWE5XHVjZDA4XHVjOWMwXHVjNWQwXHViMjk0IGlcdWJjODggXHVjMThjXHViOWNjIFx1YmMyOVx1YmFhOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHVjMThjXHVhYzAwIFx1YWUzOFx1Yzc0NCBcdWFjNzRcdWIxMTAgXHViNTRjXHViMjk0IFx1Yzc5MFx1YzJlMFx1Yzc1OCBcdWM4ODVcdWM3NDQgXHViYzI5XHViYWE5XHVkNTU4XHViMjk0IFx1YmMxOFx1YjMwMFx1ZDNiOFx1Yzc1OCBcdWJhYTlcdWNkMDhcdWM5YzBcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjODc0IFx1YjNjNFx1YzY0MFx1YzhmY1x1YWUzMCBcdWQ2MTFcdWQ2OGNcdWM1ZDAgXHVjMGM4XHViODVjIFx1YWMwMFx1Yzc4NVx1ZDU1YyBcdWMwYWNcdWI3OGNcdWI0ZTRcdWM3NDQgXHVjNzA0XHVkNTc0IFx1YjE4ZFx1YzdhNVx1Yzc1OCBcdWFkNmNcdWM4NzBcdWI5N2MgXHViMmU0XHVjMmRjIFx1YzEyNFx1YmE4NVx1ZDU2MCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YjE4ZFx1YzdhNVx1YzVkMFx1YjI5NCBcdWM3N2NcdWM3OTBcdWQ2MTUgXHVhZTM4XHVjNzc0IFx1Yzc4OFx1YWNlMCwgXHVjNTkxXHVjYWJkXHVjNWQwIFx1YmFhOVx1Y2QwOFx1YzljMFx1YWMwMCBOXHVhYzFjXHVjNTI5IFx1Yzc4OFx1YjJlNC4gXHVjNjdjXHVjYWJkIFx1YmFhOVx1Y2QwOFx1YzljMFx1YzVkMFx1YjI5NCBcdWFjMDEgXHVjODg1XHViOTU4XHVjNzU4IFx1YzE4Y1x1YWMwMCBcdWQ1NWMgXHViYWE5XHVjZDA4XHVjOWMwXHVjNTI5IFx1Y2MyOFx1YzljMFx1ZDU1OFx1YWNlMCBcdWM3ODhcdWFjZTAsIFx1YzYyNFx1Yjk3OFx1Y2FiZFx1YjNjNCBcdWI5YzhcdWNjMmNcdWFjMDBcdWM5YzBcdWM3NzRcdWIyZTQuIFx1YmFhOVx1Y2QwOFx1YzljMFx1Yzc1OCBcdWMyMWNcdWMxMWNcdWFjMDAgXHViNGE0XHVjOGZkXHViYzE1XHVjOGZkXHVjNzc0XHVjNWI0XHVjMTFjLCBhXHVjODg1XHVjNzU4IFx1YzE4Y1x1YzY0MCBiXHVjODg1XHVjNzU4IFx1YzE4Y1x1YWMwMCBcdWFjNzRcdWIxMDhcdWIyOTQgXHVhZTM4XHVjNzc0IFx1YWNiOVx1Y2U2MCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LiBcdWM4NzRcdWM3NzQgXHViYWE5XHVjZDA4XHVjOWMwIFx1YWM3NFx1YzEyNFx1YzVkMCBcdWM4ZmNcdWM3NThcdWI5N2MgXHVhZTMwXHVjNmI4XHVjNzc0XHVjOWMwIFx1YzU0YVx1Yzc0MCBcdWQwZDNcdWM3NzRcdWIyZTQuIFx1Yzc3NFx1YjU0YyAoYSxiKVx1Yjk3YyAmcXVvdDtcdWFjMDBcdWI4NWNcdWM5YzBcdWI5NzRcdWIyOTQgXHVjMzBkJnF1b3Q7XHVjNzc0XHViNzdjXHVhY2UwIFx1ZDU1OFx1Yzc5MC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHViYzg4XHVjNWQwXHViMjk0IFx1ZDZhMVx1YjJlOFx1YmNmNFx1YjNjNFx1Yjk3YyBcdWMxMjRcdWNlNThcdWQ1NThcdWFlMzAgXHVjODA0XHVjNWQwLCBcdWMwYWNcdWM3NzRcdWFjMDAgXHVjNTQ4IFx1Yzg4Ylx1YzczY1x1YmE3NFx1YzExYyBcdWFjMDBcdWI4NWNcdWM5YzBcdWI5NzRcdWIyOTQgXHVjMzBkXHVjNzc0IFx1YmE4NyBcdWFjMWNcdWM3NzhcdWM5YzAgXHVjMTM4XHVhY2UwIFx1YzJmNlx1YjJlNC4gXHVjODc0IFx1YjNjNFx1YzY0MFx1YzhmY1x1YWUzMCBcdWQ2MTFcdWQ2OGNcdWM3YTVcdWM3NTggXHVjNzg0XHVhZTMwXHVhYzAwIFx1YjJlNCBcdWIwNWRcdWIwOThcdWFjMDBcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1Yzc3NFx1YWM4M1x1Yzc3NCBcdWM2YjBcdWI5YWNcdWM1ZDBcdWFjOGMgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YjljOFx1YzljMFx1YjljOSBcdWM3ODRcdWJiMzRcdWM3NzRcdWIyZTQuIFx1YjljOFx1YzljMFx1YjljOVx1YzczY1x1Yjg1YyBcdWM4NzRcdWM3NDQgXHViM2M0XHVjNjQwXHVjOGZjXHVjNzkwLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMCBOJm5ic3A7KDEgJmxlOyBOICZsZTsgMTAwLDAwMClcdWFjZmMgSyZuYnNwOygwICZsZTsgSyAmbHQ7IE4pXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIE5cdWM5MDRcdWM1ZDBcdWIyOTQgXHVhZTM4XHVjNzU4IFx1YzY3Y1x1Y2FiZFx1YzVkMCBcdWM3ODhcdWIyOTQgXHViYWE5XHVjZDA4XHVjOWMwIFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWNjMjhcdWI4NDBcdWIzMDBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVjODg1XHVjNzQwIFx1ZDU1YyBcdWJjODhcdWM1MjkgXHViMDk4XHVkMGMwXHViMDljXHViMmU0LiBcdWFkZjggXHViMmU0XHVjNzRjIE5cdWM5MDRcdWM1ZDBcdWIyOTQgXHVhZTM4XHVjNzU4IFx1YzYyNFx1Yjk3OFx1Y2FiZFx1YzVkMCBcdWM3ODhcdWIyOTQgXHViYWE5XHVjZDA4XHVjOWMwXHVhYzAwIFx1YWMxOVx1Yzc0MCBcdWJjMjlcdWMyZGRcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YzBhY1x1Yzc3NFx1YWMwMCBcdWM1NDggXHVjODhiXHVjNzNjXHViYTc0XHVjMTFjIFx1YWMwMFx1Yjg1Y1x1YzljMFx1Yjk3NFx1YjI5NCBcdWMzMGRcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48YnI+PFwvcD4iLCJoaW50IjoiPHA+MVx1YWNmYyA0LCAxXHVhY2ZjIDNcdWM3NzQgXHVjMGFjXHVjNzc0XHVhYzAwIFx1YzU0OCBcdWM4OGJcdWM3M2NcdWJhNzRcdWMxMWMgXHVhYzAwXHViODVjXHVjOWMwXHViOTc0XHViMjk0IFx1YzMwZFx1Yzc3NFx1YjJlNC48YnI+PFwvcD4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjE0NDYwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiV2h5IERpZCB0aGUgQ293IENyb3NzIHRoZSBSb2FkIElJSSAoUGxhdGludW0pIiwiZGVzY3JpcHRpb24iOiI8cD4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RmFybWVyIEpvaG4gaXMgY29udGludWluZyB0byBwb25kZXIgdGhlIGlzc3VlIG9mIGNvd3MgY3Jvc3NpbmcgdGhlIHJvYWQgdGhyb3VnaCBoaXMgZmFybSwgaW50cm9kdWNlZCBpbiB0aGUgcHJlY2VkaW5nIHR3byBwcm9ibGVtcy4gSGUgcmVhbGl6ZXMgbm93IHRoYXQgdGhlIHRocmVzaG9sZCBmb3IgZnJpZW5kbGluZXNzIGlzIGEgYml0IG1vcmUgc3VidGxlIHRoYW4gaGUgcHJldmlvdXNseSBjb25zaWRlcmVkIC0tIGJyZWVkcyZuYnNwO2EmbmJzcDthbmQmbmJzcDtiIGFyZSBub3cgZnJpZW5kbHkgaWYmbmJzcDt8YSZtaW51cztifCAmbGU7IEssIGFuZCB1bmZyaWVuZGx5IG90aGVyd2lzZS48XC9wPlxyXG5cclxuPHA+R2l2ZW4gdGhlIG9yZGVyaW5ncyBvZiBmaWVsZHMgb24gZWl0aGVyIHNpZGUgb2YgdGhlIHJvYWQgdGhyb3VnaCBGSiYjMzk7cyBmYXJtLCBwbGVhc2UgY291bnQgdGhlIG51bWJlciBvZiB1bmZyaWVuZGx5IGNyb3NzaW5nIHBhaXJzIG9mIGJyZWVkcywgd2hlcmUgYSBjcm9zc2luZyBwYWlyIG9mIGJyZWVkcyBpcyBkZWZpbmVkIGFzIGluIHRoZSBwcmVjZWRpbmcgcHJvYmxlbXMuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMmbmJzcDtOJm5ic3A7KDEgJmxlOyBOICZsZTsgMTAwLDAwMCkgYW5kJm5ic3A7SyZuYnNwOygwICZsZTsgSyAmbHQ7IE4pLiBUaGUgbmV4dCZuYnNwO04mbmJzcDtsaW5lcyBkZXNjcmliZSB0aGUgb3JkZXIsIGJ5IGJyZWVkIElELCBvZiBmaWVsZHMgb24gb25lIHNpZGUgb2YgdGhlIHJvYWQ7IGVhY2ggYnJlZWQgSUQgaXMgYW4gaW50ZWdlciBpbiB0aGUgcmFuZ2UmbmJzcDsxJmhlbGxpcDtOLiBUaGUgbGFzdCZuYnNwO04mbmJzcDtsaW5lcyBkZXNjcmliZSB0aGUgb3JkZXIsIGJ5IGJyZWVkIElELCBvZiB0aGUgZmllbGRzIG9uIHRoZSBvdGhlciBzaWRlIG9mIHRoZSByb2FkLiBFYWNoIGJyZWVkIElEIGFwcGVhcnMgZXhhY3RseSBvbmNlIGluIGVhY2ggb3JkZXJpbmcuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlBsZWFzZSBvdXRwdXQgdGhlIG51bWJlciBvZiB1bmZyaWVuZGx5IGNyb3NzaW5nIHBhaXJzIG9mIGJyZWVkcy48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IjxwPkluIHRoaXMgZXhhbXBsZSwgYnJlZWRzIDEgYW5kIDQgYXJlIHVuZnJpZW5kbHkgYW5kIGNyb3NzaW5nLCBhcyBhcmUgYnJlZWRzIDEgYW5kIDMuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=