Cho dãy số A gồm n phần tử nguyên dương A1, A2, …, An. Mỗi phần tử có giá trị không vượt quá 109 và 1 < n ≤ 5000. Một bộ ba số được gọi là bộ số tam giác, nếu ba số này tạo thành ba cạnh của một tam giác nào đó.
Yêu cầu: Hãy đếm xem trong dãy A có bao nhiêu bộ số tam giác (Ai, Aj, Ak) với i, j, k đôi một khác nhau.
Dữ liệu vào:
- Dòng đầu là số n;
- Dòng tiếp theo là các phần tử của dãy A, mỗi phần tử cách nhau một dấu cách.
Dữ liệu ra: Ghi ra số lượng bộ số tam giác.
Input
5
4 3 1 5 7
Output
3
Giải thich ví dụ: Ba bộ số tam giác gồm: (4, 3, 5); (4, 5, 7); (3, 5, 7).
Ràng buộc:
- Có 30% số test ứng với 30% số điểm của bài có n ≤ 100.
- Có 30% số test ứng với 30% số điểm của bài có 100 < n ≤ 1000.
- Có 40% số test ứng với 40% số điểm của bài có 1000 < n ≤ 5000.
Nguồn: Bài 1 HSG lớp 12 TPĐN '2018-2019