Tam giác cân là tam giác có ít nhất hai cạnh có độ dài bằng nhau.

Cho số nguyên dương \(n\) và dãy \(n\) các số nguyên dương \(a_1,a_2,….,a_n.\)

Yêu cầu: Tính số lượng bộ ba \((i,j,k)\) với \((1≤i<j<k≤n)\) sao cho \(a_i,a_j,a_k\) là ba cạnh của một tam giác cân.

Input

• Dòng đầu ghi số nguyên \(n (3≤n≤5⋅10^5 ).\)

• Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,…,a_n (1≤a_i≤10^5 ). \)

Output

• Ghi ra một số nguyên là số lượng bộ ba tìm được.

Ràng buộc

• Subtask 1: 40% test với \(n≤10^3.\)

• Subtask 2: 30% test với \( n ≤ 10^5.\)

• Subtask 3: 30% test với ~ n ≤ 5.10^5.

Sample Input

8
5 3 2 9 5 4 9 5

Sample Output

22