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 Input: a positive integer k, and an unsorted A with n numbers, some Output: an array B of length n - k, where BlE] should contain the Write pseudocode for an algorithm for this problem with expected running interval of size k. of them repeating. number of distinct elements in the interval Ali], Ali +1]...., Ali k 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 A[i + k] to take advantage of the fact that two consecutive intervals A[i] and Afi +1]...Ali+k+1] only differ by a small number of elements