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 eaclh interval of size k. Input: a positive integer k, and an unsorted A with n numbers, some of them repeating. Output: an array B of lengthn -k+1, where Bli] should contain the number of distinct elements in the interval Ali,Ali+1],... Ali+k-1 EXAMPLE: if A 3,2,7,3,5,3,5,7,2 and k then we are looking at intervals of size k = 4, so B[1] = 3 because the subarray [3,2,7,3] has 3 distinct elements; B2]-4 because the subarray 2,7,3,5] has four distinct elements. More generally, the output array B-3,4,3,2,3,4 The question: Write pseudocode for an algorithm for this problem with expected running time O(n). Note that your expected running time should be O(n) even if k is large. A run-time of O(nk) is too slow, and will receive very little credit. HINT: similar to the algorithm for sorting a k-sorted array, you wil want to take advantage of the fact that two consecutive intervals Ali]...Ali+k and Ali.Ali k1] only differ by a small number of elements