Bộ ba

An có một dãy số nguyên \(a\) gồm \(N\) phần tử (\(1 \le N \le 3000\)).
Cậu ấy rất thích tìm các bộ ba chỉ số \((i, j, k)\) thỏa mãn:

Hãy tính xem có bao nhiêu bộ ba như vậy trong dãy.

Input

• Dòng đầu chứa một số nguyên \(N\) (\(1 \le N \le 3000\)).

• Dòng thứ hai chứa \(N\) số nguyên \(a_1, a_2, \dots, a_N\) (\(1 \le a_i \le 10^9\)).

Output

In ra một số nguyên duy nhất --- số lượng bộ ba \((i, j, k)\) thỏa mãn điều kiện.

Scoring

• Subtask 1 (50% số điểm): \(N \le 300\).

• Subtask 2 (50% số điểm): Không có ràng buộc gì thêm.

Example

Input:

4
1 2 2 3

Output:

4

Notes

Các bộ ba hợp lệ trong ví dụ: \((1,2,4), (1,3,4), (1,2,3), (2,3,4)\).