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 $[-10$

$9$

$,10$

$9],$ 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.class StaticArrayException$($Exception$)$:

$"""$

Custom exception for Static Array class.

Any changes to this class are forbidden.

$"""$

pass

class StaticArray:

$"""$

Implementation of Static Array Data Structure.

Implemented methods: get$(),$ set$(),$ length$()$

Any changes to this class are forbidden.

Even if you make changes to your StaticArray file and upload to Gradescope

along with your assignment, it will have no effect. Gradescope uses its

own StaticArray file $($a replica of this one$)$ and any extra submission of

a StaticArray file is ignored.

$"""$

def $\_\_$init$\_\_($self$,$ size: int $=10)->$ None:

$"""$

Create array of given size.

Initialize all elements with values of None.

If requested size is not a positive number,

raise StaticArray Exception.

$"""$

if size $<1$:

raise StaticArrayException$(\text{'}$Array size must be a positive integer'$)$

# The underscore denotes this as a private variable and

# private variables should not be accessed directly.

# Use the length$()$ method to get the size of a StaticArray.

self.$\_$size $=$ size

# Remember, this is a built$-$in list and is used here

# because Python doesn't have a fixed$-$size array type.

# Don't initialize variables like this in your assignments!

self.$\_$data $=[$None$]*$ size

def $\_\_$iter$\_\_($self$)->$ None:

$"""$

Disable iterator capability for StaticArray class.

This means loops and aggregate functions like

those shown below won't work:

arr $=$ StaticArray$()$

for value in arr: # will not work

min$($arr$)$ # will not work

max$($arr$)$ # will not work

sort$($arr$)$ # will not work

$"""$

return None

def $\_\_$str$\_\_($self$)->$ str:

$"""$Override string method to provide more readable output."""

return f$"$STAT$\_$ARR Size: $\{$self$.\_$size$\}\{$self$.\_$data$\}"$

def get$($self$,$ index: int$)$:

$"""$

Return value from given index position.

Invalid index raises StaticArrayException.

$"""$

if index $<0$ or index $>=$ self.length$()$:

raise StaticArrayException$(\text{'}$Index out of bounds'$)$

return self.$\_$data$[$index$]$

def set$($self$,$ index: int, value$)->$ None:

$"""$

Store value at given index in the array.

Invalid index raises StaticArrayException.

$"""$

if index $<0$ or index $>=$ self.length$()$:

raise StaticArrayException$(\text{'}$Index out of bounds'$)$

self.$\_$data$[$index$]=$ value

def $\_\_$getitem$\_\_($self$,$ index: int$)$:

$"""$Enable bracketed indexing."""

return self.get$($index$)$

def $\_\_$setitem$\_\_($self$,$ index: int, value: object$)->$ None:

$"""$Enable bracketed indexing."""

self.set$($index$,$ value$)$

def length$($self$)->$ int:

$"""$Return length of the array $($number of elements$)."""$

return self.$\_$size

if $\_\_$name$\_\_=="\_\_$main$\_\_"$:

# Using the Static Array #

# Can use either the get$/$set methods or $[]($bracketed indexing$)$ #

# Both are public methods; using the $[]$ calls the corresponding get$/$set #

# Create a new StaticArray object $-$ is the default size

arr $=$ StaticArray$()$

# These two statements are equivalent

arr.set$(0,$ 'hello'$)$

arr$[0]=$ 'hello'

# These two statements are equivalent

print$($arr$.$get$(0))$

print$($arr$[0])$

# Print the number of elements stored in the array

print$($arr$.$length$())$

# Create a new StaticArray object to store $5$ elements

arr $=$ StaticArray$(5)$

# Set the value of each element equal to its index multiplied by $10$

for index in range$($arr$.$length$())$:

arr$[$index$]=$ index $*10$

# Print the values of all elements in reverse order

for index in range$($arr$.$length$()-1,-1,-1)$:

print$($arr$[$index$]$