Tam giác cân là tam giác có ít nhất \(2\) cạnh có độ dài bằng nhau. Cho dãy gồm \(N\) số nguyên dương: \(a_1, a_2, ..., a_N\). Hãy tính số bộ \(3\) chỉ số \((i, j, k)\), với \(1 \le i \lt j \lt k \le N\) sao cho \(3\) số \(a_i, a_j, a_k\) là độ dài \(3\) cạnh của một tam giác cân.

Dữ liệu vào

• Dòng đầu ghi số nguyên \(N\) \((3 \le N \le 500000)\).
• Dòng tiếp theo ghi \(N\) số hạng của dãy, mỗi số đều không vượt quá \(10^5\). Các số hạng được ghi cách nhau bởi ít nhất một dấu cách.

Dữ liệu ra

• Một số nguyên, là số tam giác cân tìm được.

Input 1

8
5 3 2 9 5 4 9 5

Output 1

22

Ràng buộc:

• 30% số test ứng với 30% số điểm của bài ứng với \(N \lt 10^3\)
• 70% số test ứng với 70% số điểm của bài ứng với \(N \le 10^5\)