Alice và Bob là đôi bạn thân đã lâu. Vào một ngày nọ, vì cảm thấy chán nên Alice quyết định đố Bob một bài toán:

Cho \(n\) cây que, cây que thứ \(i\) \((1 \leq i \leq n)\) có độ dài \(a_{i}\). Hãy đếm số bộ ba cây que sao cho chúng có thể tạo thành ba cạnh một tam giác cân. Biết rằng, hai bộ ba được gọi là khác nhau nếu như tồn tại một cây que thứ \(i\) sao cho cây que thuộc một bộ ba và không thuộc một bộ ba còn lại (\(\{a_{1}, a_{2}, a_{3}\}\) và \(\{a_{3}, a_{2}, a_{1}\}\) là hai bộ ba giống nhau).

Input

• Dòng đầu tiên chứa số nguyên \(n\) \((1 \leq n \leq 10^{6})\) là số lượng cây que.
• Dòng tiếp theo chứa \(n\) số nguyên \(a_{1}, a_{2}, \ldots, a_{n}\) \((1 \leq a_{i} \leq 10^{9})\) là độ dài của các cây que.

Output

• In ra một số nguyên duy nhất là đáp án của bài toán.

Scoring

• Subtask \(1\) (\(42\%\) số điểm): \(n \leq 500\).
• Subtask \(2\) (\(28\%\) số điểm): \(n \leq 5000\) và \(a_{i} \leq 10^{6}\).
• Subtask \(3\) (\(16\%\) số điểm): \(a_{i} \leq 10^{6}\).
• Subtask \(4\) (\(14\%\) số điểm): Không có ràng buộc gì thêm.

Example

4
2 2 3 3 

4