Có ~N~ vị trí được xếp theo thứ tự trên một đường tròn. Vị trí thứ ~i~ mang giá trị ~a_i~. Trong dãy có đúng ~N/2~ giá trị khác nhau, mỗi giá trị xuất hiện đúng hai lần.

Với mỗi giá trị, nối hai vị trí mang giá trị đó bằng một đoạn thẳng. Hãy tính số cặp đoạn thẳng giao nhau bên trong đường tròn. Mỗi cặp đoạn giao nhau chỉ được tính một lần.

Cấu hình Input

• Dòng đầu tiên chứa số nguyên chẵn ~N~ ~(2 ≤ N ≤ 2 · 10^6)~.
• Dòng thứ hai chứa ~N~ số nguyên ~a_1, a_2, ..., a_N~ ~(1 ≤ a_i ≤ N/2)~.
• Mỗi giá trị từ ~1~ đến ~N/2~ xuất hiện đúng hai lần.

Cấu hình Output

In ra một số nguyên duy nhất là số cặp đoạn thẳng giao nhau. Kết quả có thể vượt quá phạm vi 32-bit; hãy dùng số nguyên 64-bit.

Ví dụ

Input

8
1 2 1 3 2 4 3 4

Output

3

Giải thích

Các cặp giá trị ~(1, 2)~, ~(2, 3)~ và ~(3, 4)~ tạo thành những đoạn thẳng giao nhau. Các cặp giá trị còn lại không giao nhau.

Subtasks

• Subtask 1 (10 điểm): ~N ≤ 2 · 10^3~.
• Subtask 2 (20 điểm): ~N ≤ 2 · 10^5~.
• Subtask 3 (30 điểm): ~N ≤ 10^6~.
• Subtask 4 (40 điểm): ~N ≤ 2 · 10^6~.