Cho một dãy gồm \(n\) số nguyên dương \(A_1, A_2, \dots, A_n\).

Ký hiệu \(cnt[x]\) là số lần xuất hiện của giá trị \(x\) trong dãy.

Hãy đếm số cặp chỉ số \((i, j)\) thỏa mãn:

• \(1 \le i < j \le n\)
• \(cnt[A_i] = cnt[A_j]\)

Nói cách khác, cần đếm số cặp vị trí mà hai giá trị tại các vị trí đó xuất hiện trong dãy với cùng tần suất.

Input

• 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 dương \(A_1, A_2, \dots, A_n\) (\(1 \le A_i \le 10^6\)).

Output

• In ra một số nguyên duy nhất là số cặp chỉ số \((i, j)\) thỏa mãn yêu cầu.

Example

5
1 1 2 3 3

6