Tam giác cân là tam giác có ít nhất hai 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ộ ba chỉ số \((i, j, k)\) với \(1\leq i<j<k\leq N\) sao cho cho ba số \(a_i\), \(a_j\), \(a_k\) là độ dài ba cạnh của một tam giác cân.

Input

• Dòng đầu ghi số nguyên \(N\) \((3\leq N\leq 5\cdot 10^5)\).
• Dòng tiếp theo ghi \(N\) số hạng của dãy, mỗi số hạng đề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.

Output

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

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(N\leq 10^3\)
• Subtask \(2\) (\(30\%\) số điểm): \(N\leq 10^5\)
• Subtask \(3\) (\(30\%\) số điểm): \(N\leq 5 \cdot 10^5\)

Example

8
5 3 2 9 5 4 9 5

22