Question 1. (1 marks) Suppose we have an array A[1,2,...] supporting the following two operations (where k is a global variable initially set to 0): INSERT(x) k:= k + 1 A[k] := x OUTPUTAndREDuCE for i = 1 to k do print Ali) endfor (this for loop includes k) The cost of each operation is defined as follows: . The cost of INSERT() is exactly 1. The cost of OUTPUTANDREDUCEis the exact value of the global variable k just before OUTPUTANDREDUCE) is executed (because this operation prints k elements) Let T(n) be the worst-case total cost of executing any sequence of n of the above operations, starting with k = 0, The amortized cost per operation is T(n) What is the best (i.e., smallest) upper bound for T(n) in the sorted list L below? Justify your answer (unjustified answers do not get credit). HINT: Use the accounting method and charge each INSERT the smallest amount listed in L such that the total amount charged always covers the total cost of operations