Cho mảng \(l\) gồm \(n\) số nguyên. Sắp xếp mảng tăng dần bằng bubble sort và in ra trạng thái mảng sau mỗi lần so sánh hai phần tử kề nhau.

Thuật toán: với \(i = 0 \dots n-2\), với \(j = 0 \dots n-2-i\): nếu \(l_j > l_{j+1}\) thì đổi chỗ hai phần tử. Sau mỗi lần so sánh (dù có đổi hay không), in toàn bộ mảng, đặt cặp vừa so sánh trong dấu [ ]. Không dừng sớm.

Input

• Dòng 1: số \(n\)
• Dòng 2: \(n\) số nguyên \(l_1, l_2, \dots, l_n\)

Output

• Mỗi dòng là một bước so sánh như mô tả trên
• Dòng cuối là mảng đã sắp xếp, không có dấu ngoặc

Example

5
2 5 3 4 1

[2 5] 3 4 1
2 [3 5] 4 1
2 3 [4 5] 1
2 3 4 [1 5]
[2 3] 4 1 5
2 [3 4] 1 5
2 3 [1 4] 5
[2 3] 1 4 5
2 [1 3] 4 5
[1 2] 3 4 5
1 2 3 4 5

Scoring

• \(|l_i| \le 10^9\)
• Subtask 1 (x points): \(1 \le n \le 10\)
• Subtask 2 (y points): \(1 \le n \le 100\)