Sorted Squares

You are given an array of n integers sorted in non-decreasing order. Your task is to compute a new array in which each element is the square of the corresponding element from the original array, and the resulting array is also sorted in non-decreasing order.

The problem can be solved in O(n) time complexity using a two-pointer technique. Mathematically, if the input array is \(nums = [a_0, a_1, \dots, a_{n-1}]\), you need to output an array \(result = [a'_0, a'_1, \dots, a'_{n-1}]\) such that \(a'_i = a_i^2\) (after sorting). That is, the output should be sorted. For example, given the input array \([-4, -1, 0, 3, 10]\), the output should be \([0, 1, 9, 16, 100]\).

inputFormat

The first line of input contains a single integer (n) representing the number of elements in the array. The second line contains (n) space-separated integers representing the elements of the array.

outputFormat

Output a single line containing (n) space-separated integers representing the squares of each input element, sorted in non-decreasing order.## sample

5
-4 -1 0 3 10

0 1 9 16 100