Giữ cho có thứ tự
Đề bài
Mô tả
Gon có một hoán vị của các số nguyên từ đến và muốn sắp xếp nó tăng dần. Tuy nhiên, sắp xếp thì quá dễ, ai cũng làm được!
Vì vậy, Gon quyết định chỉ dùng thao tác sau để sắp xếp:
- Chọn hai chỉ số và () sao cho đoạn con đã được sắp xếp, theo thứ tự tăng dần hoặc giảm dần.
- Đảo ngược đoạn con từ đến .
Ví dụ, với hoán vị , Gon có thể sắp xếp bằng thao tác: chọn , và đảo ngược đoạn để được .
Lưu ý nếu thì Gon không thể chọn , , vì đoạn con từ đến chưa được sắp xếp.
Vì sinh nhật của Gon là ngày 19 tháng 1, Gon muốn dùng không quá thao tác. Việc này hóa ra không hề đơn giản. Hãy giúp Gon!
Dữ liệu vào
Dòng đầu tiên chứa một số nguyên ().
Dòng thứ hai chứa số nguyên . Dữ liệu đảm bảo là một hoán vị của các số nguyên từ đến .
Dữ liệu ra
Dòng đầu tiên in ra một số nguyên () là số thao tác bạn dùng.
Mỗi dòng trong dòng tiếp theo in ra hai số nguyên và () mô tả một thao tác. Đoạn con từ đến phải đã được sắp xếp (tăng dần hoặc giảm dần) ngay trước thao tác đó.
Sau thao tác, hoán vị phải được sắp xếp tăng dần, tức là với mọi . Bạn không cần tối thiểu hóa số thao tác.
Dữ liệu đảm bảo luôn tồn tại lời giải. Nếu có nhiều lời giải, in ra một lời giải bất kỳ.
Ràng buộc
- .
- là một hoán vị của .
- Số thao tác không vượt quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 3 1 2 |
7 1 1 2 2 3 3 1 2 2 3 1 3 1 3 |
Đây là đáp án mẫu của đề gốc. Ba thao tác đầu đảo đoạn một phần tử (không đổi gì). Đảo đoạn được ; đảo đoạn được ; đoạn tăng dần nên đảo được , rồi đảo lần nữa được . Cũng có thể chỉ dùng thao tác: đảo đoạn rồi đảo đoạn . |
| 3 3 2 1 |
1 1 3 |
Ví dụ bổ sung (không có trong đề gốc). Cả hoán vị đang giảm dần nên đảo một lần là xong. |
Bình luận