Sắp xếp chọn (selection 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
5 4 3 2 1

Output

Buoc 1: 1 4 3 2 5
Buoc 2: 1 2 3 4 5
Buoc 3: 1 2 3 4 5
Buoc 4: 1 2 3 4 5

Giải thích ví dụ

Ví dụ 1

Ví dụ 2

Input

- **Buoc 1**: Chọn số nhỏ nhất từ `5 4 3 2 1` là `1`, đổi chỗ với số đầu tiên → `1 4 3 2 5`
- **Buoc 2**: Chọn số nhỏ nhất từ `4 3 2 5` là `2`, đổi chỗ với số đầu tiên của đoạn còn lại → `1 2 3 4 5`
- **Buoc 3**: Dãy đã được sắp xếp, không thay đổi → `1 2 3 4 5`
- **Buoc 4**: Dãy đã được sắp xếp, không thay đổi → `1 2 3 4 5`

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