Bố cục trang trại của Farmer John khá kỳ lạ: một con đường lớn hình tròn chạy quanh rìa cánh đồng chính, nơi đàn bò của ông gặm cỏ vào ban ngày. Mỗi sáng, đàn bò băng qua con đường này để vào cánh đồng; mỗi tối, tất cả lại băng qua đường khi rời cánh đồng và trở về chuồng.

Như chúng ta đã biết, bò là loài sống theo thói quen và mỗi con đều băng qua đường theo cùng một cách mỗi ngày. Mỗi con bò đi vào cánh đồng tại một điểm khác với điểm nó đi ra, và tất cả các điểm băng qua đường đều phân biệt. Farmer John có \(N\) con bò, được đánh dấu thuận tiện bằng các mã số nguyên từ \(1 \ldots N\), nên có chính xác \(2N\) điểm băng qua đường quanh con đường. Farmer John ghi lại các điểm này một cách ngắn gọn bằng cách đi một vòng theo chiều kim đồng hồ, viết mã số của con bò tại mỗi điểm băng qua đường, cuối cùng tạo thành một dãy \(2N\) số trong đó mỗi số xuất hiện đúng hai lần. Ông không ghi lại đâu là điểm đi vào và đâu là điểm đi ra.

Nhìn vào sơ đồ các điểm băng qua đường, Farmer John tò mò muốn biết đường đi của các cặp bò khác nhau có thể cắt nhau bao nhiêu lần trong ngày. Ông gọi một cặp bò \((a,b)\) là một cặp "giao nhau" nếu đường đi từ điểm vào đến điểm ra của bò \(a\) bắt buộc phải cắt đường đi từ điểm vào đến điểm ra của bò \(b\). Hãy giúp Farmer John đếm tổng số cặp giao nhau.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) (\(1 \leq N \leq 50,000\)), và \(2N\) dòng tiếp theo mô tả mã số bò trong dãy các điểm đi vào và đi ra quanh cánh đồng.

Dữ liệu ra

In ra tổng số cặp giao nhau.

Ví dụ

4
3
2
4
4
1
3
2
1

3

Nguồn

USACO 2017 February Contest, Gold — Why Did the Cow Cross the Road III. Tác giả đề: Brian Dean.

https://usaco.org/index.php?page=viewproblem2&cpid=719