Độ khó: Trung bình (2/4 điểm)

📖 Bài giải chi tiết: 👉 Bấm vào đây để xem lời giải cụ thể của bài này trên blog

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới bấm vào xem bài giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Cho dãy số ~A~ gồm ~n~ phần tử nguyên dương ~A_1, A_2, \ldots, A_n~. Mỗi phần tử có giá trị không vượt quá ~10^9~ và ~1 \lt n \le 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 ~(A_i, A_j, A_k)~ 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.

Kết quả

• Ghi ra số lượng bộ số tam giác.

Subtask

• Có ~30\%~ số test ứng với ~30\%~ số điểm của bài có ~n \le 100~.
• Có ~30\%~ số test ứng với ~30\%~ số điểm của bài có ~100 \lt n \le 1000~.
• Có ~40\%~ số test ứng với ~40\%~ số điểm của bài có ~1000 \lt n \le 5000~.

Sample Input 1

5
4 3 1 5 7

Sample Output 1

3

Giải thích

Ba bộ số tam giác gồm: ~(4, 3, 5)~; ~(4, 5, 7)~; ~(3, 5, 7)~.

Nguồn: Đề thi HSG lớp 12 TP Đà Nẵng năm học 2018-2019 – Bài 1.