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

Khi tìm mua bức tranh "Trúc", Cương biết rằng trên thế giới có rất nhiều chuyên gia vẽ loại tranh này. Mỗi chuyên gia vẽ "Trúc" lại vẽ cây trúc có số "đốt" khác nhau.

Vậy là Cương đã mời về ~n~ chuyên gia vẽ "Trúc", họ vẽ số đốt trúc lần lượt từ ~1~ đến ~n~, chuyên gia thứ ~i~ vẽ tranh có số đốt trúc là ~i~. Cương sẽ chọn ra người vẽ đẹp nhất và mua tranh của họ.

Anh chàng không hề biết luật ngầm trong giới vẽ "Trúc". Người nào càng vẽ được nhiều đốt lại càng giỏi.

Cương sẽ xem tranh của họ theo thứ tự nhất định. Sau khi được xem tranh, Cương sẽ cho chuyên gia đó ra về. Anh sẽ liên lạc lại họ sau nếu tranh họ đủ đẹp.

Nhưng trước khi ra về, mỗi chuyên gia, để thể hiện sự kính trọng, họ sẽ đi bắt tay với tất cả những chuyên gia giỏi hơn mình còn ở trong phòng, mỗi người một lượt. (Tội nghiệp người cuối cùng chắc chắn sẽ chẳng còn ai để bắt tay)

Thấy việc bắt tay của các chuyên gia khá hay ho — mặc dù không hiểu gì, Cương có đếm lại số lượt bắt tay của họ nhưng đôi lúc vì thấy tranh đẹp quá nên anh mải đếm. Hãy giúp Cương tính xem có chính xác bao nhiêu lượt bắt tay nhé.

Dữ liệu vào

• Dòng đầu tiên là 1 số ~n~ — số chuyên gia Cương mời đến. ~(n \le 2 \cdot 10^5)~
• Dòng thứ hai gồm ~n~ số nguyên dương ~a_i~ — thể hiện thứ tự xem tranh của Cương. Dữ liệu đảm bảo dãy đầu vào là hoán vị của các số nguyên từ ~1~ đến ~n~.

Kết quả

• Một dòng duy nhất là số lượt bắt tay sau buổi họp hôm đó.

Subtask

• ~30\%~ điểm với thứ tự ra của các chuyên gia từ bé đến lớn.
• ~40\%~ điểm với số lượng chuyên gia trong phòng không quá ~1000~.
• ~30\%~ điểm không giới hạn gì thêm.

Sample Input 1

5
3 4 2 1 5

Sample Output 1

5

Giải thích

• Người đầu tiên ra khỏi phòng là chuyên gia 3, anh bắt tay với chuyên gia 4, 5.
• Người tiếp theo ra khỏi phòng là chuyên gia 4, anh bắt tay với chuyên gia 5.
• Người tiếp theo ra khỏi phòng là chuyên gia 2, anh bắt tay với chuyên gia 5.
• Người tiếp theo ra khỏi phòng là chuyên gia 1, anh bắt tay với chuyên gia 5.
• Người cuối cùng ra khỏi phòng là chuyên gia 5, anh chẳng còn ai để bắt tay.

Tổng số lượt bắt tay là ~5~.

Nguồn: HAUI OJ – HIT Open Day 2023.