시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 19 11 9 81.818%

문제

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

존의 농장에는 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줄에는 길의 오른쪽에 있는 목초지가 같은 방식으로 주어진다.

출력

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

예제 입력

4 1
4
3
2
1
1
4
2
3

예제 출력

2

힌트

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