Sort Non-negative Numbers while Keeping Negative Numbers in Place

You are given an array of integers. Your task is to sort all the non-negative numbers in non-decreasing order while leaving the negative numbers in their original positions.

Specifically, if we denote the array as \(a_0, a_1, \dots, a_{n-1}\), then for every index \(i\) such that \(a_i \ge 0\) the value should be replaced by the corresponding value from the sorted sequence of all non-negative numbers. The positions of the negative numbers (i.e., those with \(a_i < 0\)) must remain unchanged.

Input/Output Format:
The input is given via stdin and the output should be printed to stdout.

inputFormat

The first line of input contains a single integer \(n\) which represents the number of elements in the array. The second line contains \(n\) integers separated by spaces.

outputFormat

Print the resulting array after sorting the non-negative numbers, with each element separated by a single space. If the array is empty, print nothing.

7
3 -1 4 1 -5 -9 2

1 -1 2 3 -5 -9 4