sorted$\_$squares$($arr: StaticArray$)->$ StaticArray:

Write a function that receives a StaticArray where the elements are in sorted order, and

returns a new StaticArray with squares of the values from the original array, sorted in

non$-$descending order. The original array must not be modified.

You may assume that the input array will have at least one element, will contain only

integers in the range $[-109,109],$ and that elements of the input array are already in

non$-$descending order. You do not need to write checks for these conditions.

Implement a FAST solution that can process at least $5,000,000$ elements in a reasonable

amount of time $($under a minute$).$

Note that using a traditional sorting algorithm $($even a fast sorting algorithm like merge sort

or shell sort$)$ will not pass the largest test case of $5,000,000$ elements. Also, a solution

using count$\_$sort$()$ as a helper method will also not work here, due to the wide range of

values in the input array.

For full credit, the function must be implemented with O$($N$)$ complexity.