Lại nhắc đến Chí Phèo khi xếp hàng đi mua Iphone 4S, trong lúc chờ đợi, anh lại nghĩ ra một bài toán để thử tài các bạn sinh viên PTIT.
Có tất cả N người xếp hàng. Hai người A và B sẽ nhìn thấy nhau nếu giữa 2 người không có người nào cao hơn người A hoặc B. Bạn hãy xác định số cặp người có thể nhìn thấy nhau.
Dữ liệu:
Dòng 1: Một số nguyên duy nhất N (1≤N≤500 000) là số người đứng xếp hàng.
Dòng 2..N+1: Mỗi dòng là chiều cao của một người đứng xếp hàng theo thứ tự từ đầu hàng tới cuối hàng. Chiều cao một người không quá 231.
Kết quả:
Một số nguyên duy nhất là số cặp người xếp hàng có thể nhìn thấy nhau.
Ví dụ:
|
INPUT
|
OUTPUT
|
|
7
2
4
1
2
2
5
1
|
10
|
Giải thích:
- Người ở vị trí thứ 1 có thể nhìn thấy người ở vị trí thứ 2
- Người ở vị trí thứ 2 có thể nhìn thấy người ở vị trí thứ 1,3,4,5,6
- Người ở vị trí thứ 3 có thể nhìn thấy người ở vị trí thứ 2,4
- Người ở vị trí thứ 4 có thể nhìn thấy người ở vị trí thứ 2,3,5,6
- Người ở vị trí thứ 5 có thể nhìn thấy người ở vị trí thứ 2,4,6.
- Người ở vị trí thứ 6 có thể nhìn thấy người ở vị trí thứ 2,4,5,7.
- Người ở vị trí thứ 7 có thể nhìn thấy người ở vị trí thứ 6
=> Có tất cả 10 cặp người có thể nhìn thấy nhau.
RSS