Xếp hàng
Toto chuẩn bị thi môn Phân Tích Thiết Kế Thuật toán nên ôn ngày ôn đêm, mệt quá thiếp đi trên bàn phím và bị xuyên không về thế kỷ XVIII vào ngay Quốc Tử Giám gặp bao nhiêu là sỹ tử đang xếp hàng chuẩn bị thi môn Đại thành toán pháp. Quan Chánh chủ khảo là cụ Lê Quý Đôn đang gọi thí sinh vào phòng thi trông thấy Toto liền ra bài toán như sau:
Hãy đếm xem trong dãy các sĩ tử đang xếp thành một hàng dài thẳng tắp có bao nhiêu cặp hai người nhìn thấy nhau, tức là giữa hai người không có ai cao hơn một trong hai người đó. Toto muốn quay về đi thi nhưng cụ tránh chủ khảo nói là phải trả lời được mới cho về. Bạn hãy giúp Toto nhé
Input
Dòng đầu chứa số nguyên dương \(n\) là số người đang xếp hàng \((1 \le n \le 10^5)\)
Dòng thứ 2 là chiều cao của các sĩ tử theo đơn vị thời đó là số nguyên dương có giá trị không vượt quá \(10^9\)
Output
Một số tự nhiên là kết quả bài toán
Ví dụ 1
Input
6
7 6 5 1 4 2Output
6Ví dụ 2
Input
8
4 7 2 8 4 4 4 6Output
14Giải thích ví dụ 2 Để dễ đếm cặp ta chỉ xét người trước nhìn về phía sau:
Người thứ nhất có chiều cao 4 nên chỉ nhìn thấy 1 người thứ 2
Người thứ hai có chiều cao 7 nên nhìn thấy 2 người thứ 3, thứ 4
Người thứ ba chiều cao 2 nên chỉ nhìn thấy 1 người thứ 5
Người thứ tư chiều cao 8 nên chỉ nhìn thấy 4 người thứ 5, thứ 6, thứ 7, thứ 8
Người thứ năm chiều cao 4 nên chỉ nhìn thấy 3 người thứ 6, thứ 7, thứ 8
Người thứ sáu chiều cao 4 nên chỉ nhìn thấy 2 người thứ 7, thứ 8
Người thứ bảy chiều cao 4 nên chỉ nhìn thấy 1 người thứ 8
Người thứ tám không còn ai
Comments
Em không hiểu vd 1 lắm thầy ạ, giả sử nếu xét như vd 2, thì không phải kết quả phải là 14 sao
vd1 là 7 nhìn thấy 6, 6 thấy 5, 5 thấy 1 và 4, 1 thấy 4, 4 thấy 2. Tổng là 6
em tưởng 7 nhìn thấy 6 5 1 4 2, 6 nhìn thấy 5 1 4 2, 5 nhìn thấy 1 4 2, 1 nhìn thấy 4, 4 nhìn thấy 2 ạ :v
đề bài: giữa hai người không có ai cao hơn một trong hai người đó...
À vâng ạ lỗi em, em xin lỗi, lỗi em không đọc kĩ đề ạ gomen gomen
vd 1, 6 hay 8 ạ, em đếm ra mỗi 6 :))
Cảm ơn em, thầy đã sửa ví dụ