Xếp bài
Đề bài
Mô tả
Ông Bikrone nghĩ ra trò chơi xếp bài một người như sau.
Có lá bài được xếp thành một hàng, mỗi lá ghi một số: . Ông Bikrone xem lần lượt các lá bài từ trái sang phải và chuyển một số lá về cuối hàng (đầu bên phải). Điều kiện để chuyển một lá bài là bên phải nó có ít nhất một lá bài có giá trị lớn hơn giá trị của nó. Nói chặt chẽ hơn: lá bài ở vị trí với giá trị được chuyển về cuối nếu tồn tại vị trí () sao cho .
Trò chơi diễn ra theo từng lượt. Trong một lượt, ông xem các lá bài của hàng hiện tại từ trái sang phải; các lá bài được chuyển trong lượt đó lần lượt được đặt về cuối hàng theo đúng thứ tự chúng được xem, còn điều kiện chuyển của mỗi lá chỉ xét các lá bài đứng sau nó trong hàng ở đầu lượt (xem giải thích của ví dụ 1). Trò chơi kết thúc khi ông Bikrone không thể chuyển thêm lá bài nào về cuối hàng.
Yêu cầu: Hãy giúp ông Bikrone tính tổng số lần chuyển bài cần thực hiện cho đến khi trò chơi kết thúc.
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên : số lá bài.
- Dòng thứ hai chứa số nguyên cách nhau bởi dấu cách: giá trị các lá bài theo thứ tự ban đầu từ trái sang phải.
Dữ liệu ra
In ra một số nguyên: tổng số lần chuyển bài cần thực hiện để kết thúc trò chơi.
Ràng buộc
- .
- .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 10 3 7 6 8 5 8 2 1 7 6 |
14 | Lượt 1 chuyển các lá ( lần), hàng thành . Lượt 2 chuyển ( lần), hàng thành . Lượt 3 chuyển ( lần), hàng thành . Lượt 4 chuyển ( lần), hàng thành . Lượt 5 chuyển ( lần), hàng thành . Tổng cộng . |
| 6 1 2 3 4 5 6 |
15 | Ví dụ bổ sung. Lượt đầu chuyển lá, hàng thành ; các lượt sau chuyển lần lượt lá. |
Bình luận