Sắp xếp nổi bọt (Bubble 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 nổi bọt.

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 nổi bọt.

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: 18 41 20 9 64
Buoc 2: 18 20 9 41 64
Buoc 3: 18 9 20 41 64
Buoc 4: 9 18 20 41 64

Giải thích ví dụ

Ví dụ 1 Đầu vào 41 18 64 20 9 dẫn đến các bước sắp xếp nổi bọt như sau:

• Buoc 1: 18 41 20 9 64 (sắp xếp lần đầu tiên)
• Buoc 2: 18 20 9 41 64 (sắp xếp tiếp)
• Buoc 3: 18 9 20 41 64 (sắp xếp tiếp)
• Buoc 4: 9 18 20 41 64 (hoàn thành)

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: 20