Please provide detailed steps and explanation. Thank you!

You are working on a project modelling COVID-19 positive test counts. You have an array A of two-element tuples where the first element is a date and the second element is the number of positive tests on that date. The array is sorted in date order with earlier dates first. You have been asked to compute a new array as follows. Each output element i corresponds to input element i. It holds the number of days from input day i until the future date in the input array that has the closest test count to the count on day i without being over the count on day i. If there is no future date with a test count lower than a given day, that element in the output array should be set to 0. Here is an example input array: [(2021/01/01, 3363), (2021/01/02, 2964), (2021/01/07, 4249), (2021/01/11, 2903), (2021/01/15, 3056), (2021/01/16, 3422), (2021/02/01, 1172), (2021/02/04, 1670), (2021/02/09, 1072) ] and the corresponding expected output: [14, 9, 9, 24, 20, 19, 8, 5, 0] In your algorithm you may use the statement A[i].date - A[j].date to determine the number of days between tuples A[i] and A[j]. This is an O(1) call. (a) The obvious naive algorithm takes O(na) time. Describe this algorithm. (b) Design an algorithm and supporting data structure to implement this task in asymptotically less time. Describe the algorithm including any data structures it uses. (c) State and justify the worst-case complexity of your algorithm