시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 28 14 12 75.000%

문제

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

존의 농장에는 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+XHVjODc0IFx1YjNjNFx1YzY0MFx1YzhmY1x1YWUzMCBcdWQ2MTFcdWQ2OGNcdWM1ZDAgXHVjMGM4XHViODVjIFx1YWMwMFx1Yzc4NVx1ZDU1YyBcdWMwYWNcdWI3OGNcdWI0ZTRcdWM3NDQgXHVjNzA0XHVkNTc0IFx1YjE4ZFx1YzdhNVx1Yzc1OCBcdWFkNmNcdWM4NzBcdWI5N2MgXHViMmU0XHVjMmRjIFx1YzEyNFx1YmE4NVx1ZDU2MCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YjE4ZFx1YzdhNVx1YzVkMFx1YjI5NCBcdWM3N2NcdWM3OTBcdWQ2MTUgXHVhZTM4XHVjNzc0IFx1Yzc4OFx1YWNlMCwgXHVjNTkxXHVjYWJkXHVjNWQwIFx1YmFhOVx1Y2QwOFx1YzljMFx1YWMwMCBOXHVhYzFjXHVjNTI5IFx1Yzc4OFx1YjJlNC4gXHVjNjdjXHVjYWJkIFx1YmFhOVx1Y2QwOFx1YzljMFx1YzVkMFx1YjI5NCBcdWFjMDEgXHVjODg1XHViOTU4XHVjNzU4IFx1YzE4Y1x1YWMwMCBcdWQ1NWMgXHViYWE5XHVjZDA4XHVjOWMwXHVjNTI5IFx1Y2MyOFx1YzljMFx1ZDU1OFx1YWNlMCBcdWM3ODhcdWFjZTAsIFx1YzYyNFx1Yjk3OFx1Y2FiZFx1YjNjNCBcdWI5YzhcdWNjMmNcdWFjMDBcdWM5YzBcdWM3NzRcdWIyZTQuIFx1YmFhOVx1Y2QwOFx1YzljMFx1Yzc1OCBcdWMyMWNcdWMxMWNcdWFjMDAgXHViNGE0XHVjOGZkXHViYzE1XHVjOGZkXHVjNzc0XHVjNWI0XHVjMTFjLCBhXHVjODg1XHVjNzU4IFx1YzE4Y1x1YzY0MCBiXHVjODg1XHVjNzU4IFx1YzE4Y1x1YWMwMCBcdWFjNzRcdWIxMDhcdWIyOTQgXHVhZTM4XHVjNzc0IFx1YWNiOVx1Y2U2MCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LiBcdWM4NzRcdWM3NzQgXHViYWE5XHVjZDA4XHVjOWMwIFx1YWM3NFx1YzEyNFx1YzVkMCBcdWM4ZmNcdWM3NThcdWI5N2MgXHVhZTMwXHVjNmI4XHVjNzc0XHVjOWMwIFx1YzU0YVx1Yzc0MCBcdWQwZDNcdWM3NzRcdWIyZTQuIFx1Yzc3NCBcdWI1NGMgKGEsYilcdWI5N2MgJnF1b3Q7XHVhYzAwXHViODVjXHVjOWMwXHViOTc0XHViMjk0IFx1YzMwZCZxdW90O1x1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWQ1NThcdWM3OTAuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1YmM4OFx1YzVkMFx1YjI5NCBcdWQ2YTFcdWIyZThcdWJjZjRcdWIzYzRcdWI5N2MgXHVjMTI0XHVjZTU4XHVkNTU4XHVhZTMwIFx1YzgwNFx1YzVkMCwgXHVjMGFjXHVjNzc0XHVhYzAwIFx1YzU0OCBcdWM4OGJcdWM3M2NcdWJhNzRcdWMxMWMgXHVhYzAwXHViODVjXHVjOWMwXHViOTc0XHViMjk0IFx1YzMwZFx1Yzc3NCBcdWJhODcgXHVhYzFjXHVjNzc4XHVjOWMwIFx1YzEzOFx1YWNlMCBcdWMyZjZcdWIyZTQuIFx1Yzg3NCBcdWIzYzRcdWM2NDBcdWM4ZmNcdWFlMzAgXHVkNjExXHVkNjhjXHVjN2E1XHVjNzU4IFx1Yzc4NFx1YWUzMFx1YWMwMCBcdWIyZTQgXHViMDVkXHViMDk4XHVhYzAwXHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWM3NzRcdWFjODNcdWM3NzQgXHVjNmIwXHViOWFjXHVjNWQwXHVhYzhjIFx1YzhmY1x1YzViNFx1YzljNCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjNzg0XHViYjM0XHVjNzc0XHViMmU0LiBcdWI5YzhcdWM5YzBcdWI5YzlcdWM3M2NcdWI4NWMgXHVjODc0XHVjNzQ0IFx1YjNjNFx1YzY0MFx1YzhmY1x1Yzc5MC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWM5MDRcdWM1ZDAgTiZuYnNwOygxICZsZTsgTiAmbGU7IDEwMCwwMDApXHVhY2ZjIEsmbmJzcDsoMCAmbGU7IEsgJmx0OyBOKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBOXHVjOTA0XHVjNWQwXHViMjk0IFx1YWUzOFx1Yzc1OCBcdWM2N2NcdWNhYmRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YmFhOVx1Y2QwOFx1YzljMCBcdWJjODhcdWQ2MzhcdWFjMDAgXHVjYzI4XHViODQwXHViMzAwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1Yzg4NVx1Yzc0MCBcdWQ1NWMgXHViYzg4XHVjNTI5IFx1YjA5OFx1ZDBjMFx1YjA5Y1x1YjJlNC4gXHVhZGY4IFx1YjJlNFx1Yzc0YyBOXHVjOTA0XHVjNWQwXHViMjk0IFx1YWUzOFx1Yzc1OCBcdWM2MjRcdWI5NzhcdWNhYmRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YmFhOVx1Y2QwOFx1YzljMFx1YWMwMCBcdWFjMTlcdWM3NDAgXHViYzI5XHVjMmRkXHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWMwYWNcdWM3NzRcdWFjMDAgXHVjNTQ4IFx1Yzg4Ylx1YzczY1x1YmE3NFx1YzExYyBcdWFjMDBcdWI4NWNcdWM5YzBcdWI5NzRcdWIyOTQgXHVjMzBkXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPGJyPjxcL3A+IiwiaGludCI6IjxwPjFcdWFjZmMgNCwgMVx1YWNmYyAzXHVjNzc0IFx1YzBhY1x1Yzc3NFx1YWMwMCBcdWM1NDggXHVjODhiXHVjNzNjXHViYTc0XHVjMTFjIFx1YWMwMFx1Yjg1Y1x1YzljMFx1Yjk3NFx1YjI5NCBcdWMzMGRcdWM3NzRcdWIyZTQuPGJyPjxcL3A+Iiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxNDQ2MCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IldoeSBEaWQgdGhlIENvdyBDcm9zcyB0aGUgUm9hZCBJSUkgKFBsYXRpbnVtKSIsImRlc2NyaXB0aW9uIjoiPHA+Jm5ic3A7PFwvcD5cclxuXHJcbjxwPkZhcm1lciBKb2huIGlzIGNvbnRpbnVpbmcgdG8gcG9uZGVyIHRoZSBpc3N1ZSBvZiBjb3dzIGNyb3NzaW5nIHRoZSByb2FkIHRocm91Z2ggaGlzIGZhcm0sIGludHJvZHVjZWQgaW4gdGhlIHByZWNlZGluZyB0d28gcHJvYmxlbXMuIEhlIHJlYWxpemVzIG5vdyB0aGF0IHRoZSB0aHJlc2hvbGQgZm9yIGZyaWVuZGxpbmVzcyBpcyBhIGJpdCBtb3JlIHN1YnRsZSB0aGFuIGhlIHByZXZpb3VzbHkgY29uc2lkZXJlZCAtLSBicmVlZHMmbmJzcDthJm5ic3A7YW5kJm5ic3A7YiBhcmUgbm93IGZyaWVuZGx5IGlmJm5ic3A7fGEmbWludXM7YnwgJmxlOyBLLCBhbmQgdW5mcmllbmRseSBvdGhlcndpc2UuPFwvcD5cclxuXHJcbjxwPkdpdmVuIHRoZSBvcmRlcmluZ3Mgb2YgZmllbGRzIG9uIGVpdGhlciBzaWRlIG9mIHRoZSByb2FkIHRocm91Z2ggRkomIzM5O3MgZmFybSwgcGxlYXNlIGNvdW50IHRoZSBudW1iZXIgb2YgdW5mcmllbmRseSBjcm9zc2luZyBwYWlycyBvZiBicmVlZHMsIHdoZXJlIGEgY3Jvc3NpbmcgcGFpciBvZiBicmVlZHMgaXMgZGVmaW5lZCBhcyBpbiB0aGUgcHJlY2VkaW5nIHByb2JsZW1zLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zJm5ic3A7TiZuYnNwOygxICZsZTsgTiAmbGU7IDEwMCwwMDApIGFuZCZuYnNwO0smbmJzcDsoMCAmbGU7IEsgJmx0OyBOKS4gVGhlIG5leHQmbmJzcDtOJm5ic3A7bGluZXMgZGVzY3JpYmUgdGhlIG9yZGVyLCBieSBicmVlZCBJRCwgb2YgZmllbGRzIG9uIG9uZSBzaWRlIG9mIHRoZSByb2FkOyBlYWNoIGJyZWVkIElEIGlzIGFuIGludGVnZXIgaW4gdGhlIHJhbmdlJm5ic3A7MSZoZWxsaXA7Ti4gVGhlIGxhc3QmbmJzcDtOJm5ic3A7bGluZXMgZGVzY3JpYmUgdGhlIG9yZGVyLCBieSBicmVlZCBJRCwgb2YgdGhlIGZpZWxkcyBvbiB0aGUgb3RoZXIgc2lkZSBvZiB0aGUgcm9hZC4gRWFjaCBicmVlZCBJRCBhcHBlYXJzIGV4YWN0bHkgb25jZSBpbiBlYWNoIG9yZGVyaW5nLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5QbGVhc2Ugb3V0cHV0IHRoZSBudW1iZXIgb2YgdW5mcmllbmRseSBjcm9zc2luZyBwYWlycyBvZiBicmVlZHMuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiI8cD5JbiB0aGlzIGV4YW1wbGUsIGJyZWVkcyAxIGFuZCA0IGFyZSB1bmZyaWVuZGx5IGFuZCBjcm9zc2luZywgYXMgYXJlIGJyZWVkcyAxIGFuZCAzLjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d