C11PAIRS - Đếm cặp
Giới hạn- Thời gian: 1.0s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
N người đang đứng xếp hàng chờ mua vé vào buổi hòa nhạc. Mọi người đều phát chán khi phải chờ đợi, vì vậy họ nhìn quanh xem có ai quen hay không.
Hai người A và B đứng trong hàng có thể nhìn thấy nhau nếu:
- Người A và người B đang đứng cạnh nhau.
- Giữa người A và người B, không có ai cao hơn hẳn một trong hai người.
Hãy đếm xem có bao nhiêu cặp có thể nhìn thấy nhau trong hàng.
Dữ liệu
- Dòng đầu tiên chứa số nguyên dương N, là số người đang đứng trong hàng.
- Mỗi dòng trong N dòng tiếp theo chứa một số nguyên là chiều cao của một người tính bằng nanomet. (Tất cả mọi người đều thấp hơn 2 31 nanomet).
Kết quả
- Một số nguyên duy nhất là kết quả cần tìm.
Ví dụ
Input:
7
2
4
1
2
2
5
1
Output:
10
Giải thích
Các cặp có thể nhìn thấy nhau là (1, 2), (2, 3), (2, 4), (2, 5), (2, 6), (3, 4), (4, 5), (4, 6), (5, 6), (6, 7).
Giới hạn
- 1 ≤ N ≤ 5.10 5
- Trong 1/3 số test 1 ≤ N ≤ 5000
- Người up: tohuuquan