Perform the operation just as instructed in the problem statement. There are several possible implementations.

The naivest implementation is as follows:

sample code (Python).

But you don’t need to scan the array twice, both in steps 1 and 2. We can escape from the loop if step 2 was never performed, like this:

sample code (Python).

Then it turns out that you can resume from the last insertion position to avoid scanning the array multiple times:

sample code (Python).

In step 2, it is sufficient to insert only one first element to be added:

sample code (Python),
実装例(C++).

About the execution time

In the implementation above, we actually insert numbers into the original array. In most languages, such an insertion costs a time proportional to the number of elements after the insertion position. Thus, the worst total execution time is \(\Omega(N^2+M)\), where \(M\) is the length of the sequence to print. Instead of inserting a number into the sequence, we can incrementally construct a new sequence that results in the answer to finish the entire operation in an \(O(M)\) time. When you are to try Problem C and later, do consider the complexity of the process too.

Sample code (Python) (constructs a new array)
Sample code (C) (prints every element once it’s ready, without maintaining the resulting sequence)