5 Problem 5 (20 points) Consider the following problem, where we are given an array A with some duplicate elements, and want to find the number of distinct elements in each interval of size k Input: a positive integer k, and an unsorted A with n numbers, some Output: an array B of length n - k, where Bl] should contain the Write pseudocode for an algorithm for this problem with expected running of them repeating number of distinct elements in the interval Alt], Ali+1],, A time O(n). Note that your expected running time should be O(n) even if k is large. HINT: similar to the algorithm for sorting a k-sorted array, you will want to take advantage of the fact that two consecutive intervals A[i] A[ and A.Ali k+1] only differ by a small number of elements