Sắp xếp chèn (Insertion sort).

Bối cảnh

Bài toán được mô tả qua yêu cầu và dữ liệu dưới đây.

Yêu cầu

Cho một dãy số \(a\) có \(N\) phần từ \(a_1, a_2, a_3,...a_n\). Hãy in ra các bước của thuật toán sắp xếp chèn.

Input

Dòng đầu tiên là số nguyên dương \(N\) \(1 \leq N \leq 10^3\).

Dòng thứ hai chứa \(N\) số nguyên, mỗi số các nhau một dấu cách \((|a_i| < 10^{18})\)

Output

In ra các bước của thuật toán sắp xếp chèn.

Ràng buộc

Đề gốc không nêu ràng buộc riêng.

Ví dụ 1

Input

5
41 18 64 20 9

Output

Buoc 1: 41 18 64 20 9
Buoc 2: 18 41 64 20 9
Buoc 3: 18 41 64 20 9
Buoc 4: 18 20 41 64 9
Buoc 5: 9 18 20 41 64

Giải thích ví dụ

Ví dụ 1

Ví dụ 2

Input

- **Buoc 1**: `41 18 64 20 9` (không thay đổi)
- **Buoc 2**: Chèn `18` vào vị trí đúng → `18 41 64 20 9`
- **Buoc 3**: `18 41 64 20 9` (không thay đổi)
- **Buoc 4**: Chèn `20` vào vị trí đúng → `18 20 41 64 9`
- **Buoc 5**: Chèn `9` vào vị trí đúng → `9 18 20 41 64`

Thông tin học tập

• Buổi: B16
• Concepts: sorting, basic searching
• Giới hạn kiến thức: B01-B16
• Time limit: 2 seconds
• Memory limit: 20 MB
• Point: 10