Q1. In an online game, a list of scores achieved by people who played the game is maintained. Each time a new person completes the game, the list gets extended by his/her score. To prevent the list from becoming prohibitively long, the bottom 25% scores are dropped from the list at certain points in time. It is required to design an ecient data structure S to maintain the scores and support the two operations Insert and Drop: (I) Show how to implement this data structure such that the amortized cost per any of the above two operations is O(1). Your implementation should also include a way to output the elements of S in O(|S|) time. (II) Using the aggregate method, show that the amortized cost per (Insert or Drop) operation is O(1); (III) Repeat (II) using the accounting method; (IV) Repeat (II) using the potential method; (V) Write a Python procedure DS(scores) implementing the above data structure. Your code should accept an input list containing the scores and a number of "-1's" marking the deletions. The program should output the final list.

For instance: DS[1; 2; 9; 5;-1; 8; 3; 1; 3; 2; 9;-1; 8] should return "[9; 5; 8; 3; 3; 9; 8]". Note: for an integer n, interpret as roof