In the previous problem, we designed a data structure supporting the following operations BUILD(A1..n]): Initializes the data structure with the elements of the array A in time O(n) INSERT(x): Inserts the element r into the data structure in time O(log n), where n is the number of elements stored in the data structure MEDIAN: Returns the median2 in time O(1) of the currently stored elements In this problem we assume that all elements are integer numbers from 1 to 106, and we will design a data structure that supports the same set of operations but inserts an element in constant time (a) (3 points) Describe in English an idea for a data structure such that you can perform the operations BUILD, INSERT, and MEDIAN with running times as required below. Do not for- mally analyze the running time Solution: INSERT YOUR SOLUTION HERE In parts (b)-(d), describe in pseudo-code your implementations from part (a) and analyze the running time (b) (3 points) BUILD running in time O(n) Solution: INSERT YOUR SOLUTION HERE (c) (1 points) INSERT running in time O(1), and Solution: INSERT YOUR SOLUTION HERE (d) (3 points) MEDIAN running in time O(1) Solution: INSERT YOUR SOLUTION HERE In the previous problem, we designed a data structure supporting the following operations BUILD(A1..n]): Initializes the data structure with the elements of the array A in time O(n) INSERT(x): Inserts the element r into the data structure in time O(log n), where n is the number of elements stored in the data structure MEDIAN: Returns the median2 in time O(1) of the currently stored elements In this problem we assume that all elements are integer numbers from 1 to 106, and we will design a data structure that supports the same set of operations but inserts an element in constant time (a) (3 points) Describe in English an idea for a data structure such that you can perform the operations BUILD, INSERT, and MEDIAN with running times as required below. Do not for- mally analyze the running time Solution: INSERT YOUR SOLUTION HERE In parts (b)-(d), describe in pseudo-code your implementations from part (a) and analyze the running time (b) (3 points) BUILD running in time O(n) Solution: INSERT YOUR SOLUTION HERE (c) (1 points) INSERT running in time O(1), and Solution: INSERT YOUR SOLUTION HERE (d) (3 points) MEDIAN running in time O(1) Solution: INSERT YOUR SOLUTION HERE