Độ khó: Khá (3/4 điểm)

🎓 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

Trong đêm hội trăng rằm, trên con phố đi bộ người ta treo ~N~ chiếc đèn lồng thành một hàng, đánh số từ ~1~ đến ~N~ theo thứ tự từ trái sang phải. Chiếc đèn thứ ~i~ có độ sáng ~a_i~.

Thầy Sơn rất thích chụp ảnh. Thầy chọn hai chiếc đèn ~l < r~ làm hai mép của bức ảnh. Bức ảnh được gọi là hài hòa nếu mọi chiếc đèn nằm giữa hai mép (tức các đèn ~l+1, l+2, \dots, r-1~) đều không sáng hơn bất kỳ đèn mép nào, nói cách khác:

~\max(a_{l+1}, a_{l+2}, \dots, a_{r-1}) \le \min(a_l, a_r)~.

Nếu ~r = l + 1~ (không có đèn nào ở giữa) thì bức ảnh luôn hài hòa.

Hãy đếm số cặp ~(l, r)~ với ~1 \le l < r \le N~ tạo thành bức ảnh hài hòa.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên ~N~ ~(1 \le N \le 3 \times 10^5)~.
• Dòng thứ hai chứa ~N~ số nguyên ~a_1, a_2, \dots, a_N~ ~(1 \le a_i \le 10^9)~.

Kết quả

Một số nguyên duy nhất là số cặp ~(l, r)~ thỏa mãn.

Giới hạn (Subtask)

• Subtask 1 (~30\%~ số điểm): ~N \le 3000~.
• Subtask 2 (~30\%~ số điểm): các giá trị ~a_i~ đôi một khác nhau.
• Subtask 3 (~40\%~ số điểm): không có ràng buộc gì thêm.

💡 Lưu ý khi nộp bằng Python: các em nên chọn ngôn ngữ PyPy 3 thay vì Python 3 để chương trình chạy nhanh hơn nhiều. Giới hạn thời gian cho Python/PyPy ở bài này là 2 giây.

Sample Input 1

5
4 2 3 2 5

Sample Output 1

7

Giải thích

Các cặp hài hòa là: ~(1,2), (2,3), (3,4), (4,5)~ (kề nhau), ~(1,3)~ (giữa là ~2 \le \min(4,3)~), ~(3,5)~ (giữa là ~2 \le \min(3,5)~) và ~(1,5)~ (giữa lớn nhất là ~3 \le \min(4,5)~). Cặp ~(2,4)~ không hài hòa vì đèn giữa có độ sáng ~3 > 2~.

Nguồn: Đề tự luyện HSG Tin học lớp 9 (đề tự soạn).