소가 길을 건너간 이유 9

이 이야기는 존이 농장을 개편하기 전의 일이다.

존의 농장에는 원형 목초지가 있고 그 둘레를 길이 감싸고 있다. 존의 소는 매일 아침 이 길을 건너 목초지로 가서 풀을 먹고, 저녁에 다시 길을 건너 헛간으로 돌아간다.

소들은 습관대로 매일 똑같은 방법으로 길을 건넌다. 각 소는 원형 길 위의 정해진 한 점을 지나 들어오고 다른 한 점을 지나 나간다. 어떤 두 소도 길 위의 같은 점을 지나가지 않는다. 이를 지켜본 존은 이 점들을 분석해 보기로 했다. 소는 모두 $N$마리이고 $1, 2, \ldots, N$의 번호가 붙어 있다. (원래는 A부터 Z까지의 이름으로 소를 불렀지만 소가 많아지면서 그 방법을 더 쓸 수 없게 되었다.) 존은 $2N$개의 점을 시계 방향으로 따라가며 각 점을 지나가는 소의 번호를 기록했다. 이렇게 만든 길이 $2N$의 수열에는 각 번호가 정확히 두 번씩 나타난다.

어떤 두 소는 어떻게 걷더라도 경로가 어딘가에서 반드시 만난다. 이런 소의 쌍이 모두 몇 개인지 구하시오.

첫째 줄에 $N$ $(1 \le N \le 50\,000)$이 주어진다. 다음 $2N$개의 줄에는 길 위의 점을 시계 방향 순서대로 하나씩, 그 점을 지나가는 소의 번호가 주어진다. $1$부터 $N$까지의 각 번호는 정확히 두 번씩 나타난다.

경로가 반드시 만나는 소의 쌍의 개수를 출력한다.