Cho mảng A gồm N phần tử. Đếm số cặp \((i, j)\) sao cho i < j và A[i] = A[j].

Sử dụng rời rạc hoá kết hợp mảng đếm tần số để đếm số cặp trùng nhau một cách hiệu quả.

Đầu vào

• Dòng đầu tiên chứa số nguyên N (\(1 \le N \le 10^5\)).
• Dòng thứ hai chứa N số nguyên \(A_i\) (\(-10^9 \le A_i \le 10^9\)).

Đầu ra

Một số nguyên duy nhất là số cặp thoả mãn.

Ví dụ

Input:
6
3 1 3 1 1 2

Output:
4

Giải thích

Các cặp: \((0, 2)\) với A[0]=A[2]=3; \((1, 3)\), \((1, 4)\), \((3, 4)\) với A[1]=A[3]=A[4]=1.

Ràng buộc & Subtasks