Sorted Squares of a Sorted Array

You are given a sorted array of integers in non-decreasing order. Your task is to return an array that contains the square of each number from the input array, with the resulting array also sorted in non-decreasing order.

For example, if the input array is [-4, -1, 0, 3, 10], then the output should be [0, 1, 9, 16, 100]. An optimal solution uses the two-pointer method to achieve this in linear time.

Note: The program should read from stdin and output to stdout.

inputFormat

The first line of input contains an integer n which is the number of elements in the array. The second line contains n space-separated integers representing the array elements.

outputFormat

Output a single line containing the squares of the input numbers sorted in non-decreasing order, separated by spaces.

## sample

5
-4 -1 0 3 10

0 1 9 16 100

</p>