Độ 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

---

Bài toán gốc trên LeetCode được chuyển sang dạng nhập/xuất chuẩn (stdin/stdout).

Có ~n~ người lính đứng thành một hàng. Mỗi người lính được gán một giá trị rating duy nhất (không trùng với ai khác).

Bạn phải lập một đội gồm 3 người lính trong số họ theo các quy tắc sau:

• Chọn 3 người lính có chỉ số ~(i, j, k)~ với rating lần lượt là ~(~rating[i], rating[j], rating[k]~)~.
• Một đội là hợp lệ nếu: ~(~rating[i] ~\lt~ rating[j] ~\lt~ rating[k]~)~ hoặc ~(~rating[i] ~\gt~ rating[j] ~\gt~ rating[k]~)~, trong đó ~0 \le i \lt j \lt k \lt n~.

Hãy trả về số đội bạn có thể lập được thỏa các điều kiện trên. (Một người lính có thể thuộc nhiều đội khác nhau.)

Dữ liệu vào

• Dòng đầu là số nguyên ~n~.
• Dòng thứ hai gồm ~n~ số nguyên rating[0], rating[1], ..., rating[n-1].

Kết quả

• Một số nguyên là số đội hợp lệ.

Giới hạn

• ~n ==~ rating.length
• ~3 \le n \le 1000~
• ~1 \le~ rating[i] ~\le 10^5~
• Tất cả các số trong rating đều khác nhau.

Sample Input 1

5
2 5 3 4 1

Sample Output 1

3

Giải thích

Lập được 3 đội thỏa điều kiện: ~(2, 3, 4)~, ~(5, 4, 1)~, ~(5, 3, 1)~.

Sample Input 2

3
2 1 3

Sample Output 2

0

Giải thích

Không lập được đội nào thỏa điều kiện.

Sample Input 3

4
1 2 3 4

Sample Output 3

4

Giải thích

Mảng tăng dần nên chọn 3 người bất kỳ đều được: ~\binom{4}{3} = 4~ đội.

Nguồn: LeetCode 1395.