Để sắp xếp tăng dần một mảng \(n\) phần tử \(a_{0}, a_{1}, ... , a_{n - 1}\) (chỉ số bắt đầu từ \(0\)). Thuật toán sắp xếp chèn thực hiện \(n - 1\) bước. Tại bước \(i\), chèn phần tử \(a_{i}\) vào các phần tử \(a_{0}, a_{1}, ... , a_{i - 1}\) sao cho dãy kết quả \(a_{0}, a_{1}, ... , a_{i}\) là tăng dần.
Ví dụ minh họa: Sắp xếp mảng \(6\) phần tử: \(8\) \(5\) \(2\) \(7\) \(9\) \(3\)

• Sau bước \(1\): \(5\) \(8\) \(2\) \(7\) \(9\) \(3\)
• Sau bước \(2\): \(2\) \(5\) \(8\) \(7\) \(9\) \(3\)
• Sau bước \(3\): \(2\) \(5\) \(7\) \(8\) \(9\) \(3\)
• Sau bước \(4\): \(2\) \(5\) \(7\) \(8\) \(9\) \(3\)
• Sau bước \(5\): \(2\) \(3\) \(5\) \(7\) \(8\) \(9\)

Giải thích:

• Tại bước \(1\), số \(5\) chèn vào vị trí \(0\);
• Tại bước \(2\), số \(2\) được chèn vào vị trí \(0\);
• Tiếp theo, số \(7\) được chèn vào vị trí \(2\);
• Tiếp theo số \(9\) giữ nguyên vị trí \(4\);
• Cuối cùng số \(3\) chèn vào vị trí \(1\).

Cho mảng \(n\) phần tử bất kỳ, bạn hãy cho biết tại mỗi bước thực hiện như trên thì số nào được chèn vào vị trí nào nhé.

Input

• Dòng đầu tiên là số nguyên \(n\) \((2 \leq n \leq 20)\) là số phần tử của mảng.
• Dòng tiếp theo gồm \(n\) số nguyên \(a_{0}, a_{1}, ... , a_{n - 1}\) \((1 \leq a_{i} \leq 100)\), mỗi số cách nhau một khoảng trắng.

Output

• Gồm \(n - 1\) dòng thể hiện \(n - 1\) bước.
• Tại dòng \(i\) là \(2\) số nguyên \(a_{i}\) và \(k\) cách nhau một khoảng trắng. \(k\) là vị trí cần chèn của \(a_{i}\).

Example

6
8 5 2 7 9 3

5 0
2 0
7 2
9 4
3 1