Cho một dãy số nguyên \(a\) gồm \(n\) phần tử \(a_1, a_2, \ldots, a_n\). Xét bộ ba các chỉ số \(i, j, k\) với \(1 \le i < j < k \le n\). Một bộ ba được gọi là “thú vị” nếu trong \(a_i, a_j, a_k\) có đúng hai phần tử bằng nhau, phần tử còn lại có giá trị khác biệt. Thí dụ, các bộ ba giá trị \((3,6,3)\) và \((1,1,5)\) là “thú vị”, trong khi \((9,9,9)\) và \((1,2,3)\) thì không.

Yêu cầu: Cho dãy \(a\), hãy đếm số lượng bộ ba “thú vị” có trong dãy.

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) \((1 \le n \le 3 \cdot 10^5)\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, a_3, \ldots, a_n\) \((1 \le a_i \le 10^6)\).

Output

• Một số nguyên duy nhất là số lượng bộ ba đếm được.

Example

4
1 1 1 2

3

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \le 100\).
• Subtask \(2\) (\(30\%\) số điểm): \(n \le 3000\).
• Subtask \(3\) (\(25\%\) số điểm): \(a_i \le 3000\).
• Subtask \(4\) (\(15\%\) số điểm): không có ràng buộc thêm.