Sorted Squares Transformation

Given an array of n integers sorted in non-decreasing order, compute a new array which consists of the squares of each number, also sorted in non-decreasing order.

Let the input array be \(a_0, a_1, \ldots, a_{n-1}\). You are to produce an array \(r\) such that \(r[i] = a[i]^2\) for all \(i\) and \(r\) is sorted in non-decreasing order.

Note: The input array may contain negative numbers. A recommended approach is to use the two-pointer technique with a time complexity of \(O(n)\).

inputFormat

The first line of input contains an integer n representing the number of elements in the array.

The second line contains n space-separated integers representing the array elements in non-decreasing order.

outputFormat

Output a single line containing n space-separated integers representing the squares of each input number, sorted in non-decreasing order.

5
-4 -1 0 3 10

0 1 9 16 100