소는 왜 길을 건너갔을까? 12 timer 2s memory 512MB

농장에는 일자 모양의 길이 있고, 양쪽에 목초지가 각각 N개씩있다. 소의 종류별로 목초지 구조가 너무 달라서 한 목초지에는 정해진 종류의 소만 방목할 수 있다. i번 목초지에는 i번 종류의 소만 방목할 수 있다.

존의 농장에는 N 종류의 소가 있다. 각각 1, ..., N번 종류이다. 만약 |a−b| ≤ K라면 a번 종과 b번 종의 소는 친하지만, 그렇지 않으면 사이가 좋지 않다. 소는 길을 건널 때는 자신과 같은 종류의 소를 방목하는 반대편의 목초지로 이동한다.

목초지의 순서가 뒤죽박죽이어서, a 종류의 소와 b 종류의 소가 건너는 길이 교차할 수도 있다. 이때 (a,b)를 "교차하는 쌍"이라고 하자.

이 때, 사이가 좋지 않은 소들이 교차를 하면 싸움이 생길 수가 있기에 존은 사이가 좋지 않으면서 교차하는 쌍의 수를 알고싶다.