c++ Để sắp xếp tăng dần một mảng n phần tử a0, a1,..., an-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ử ai vào các phần tử a0, a1,..., ai-1 sao cho dãy kết quả a0, a1,..., ai 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 (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é. Dữ liệu nhập: - Dòng đầu tiên là số nguyên n (2 n 20) là số phần tử của mảng. - Dòng tiếp theo gồm n số nguyên a0, a1,..., an-1 (1  ai  100), mỗi số cách nhau một khoảng trắng. Dữ liệu xuất: gồm n - 1 dòng thể hiện n - 1 bước - Tại dòng i là 2 số nguyên ai và k cách nhau một khoảng trắng. k là vị trí cần chèn của ai Ví dụ input 6 8 5 2 7 9 3 output 5 0 2 0 7 2 9 4 3 1