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 of them repeating.

Output: an array B of length n k, where B[i] should contain the number of distinct elements in the interval A[i], A[i + 1], ..., A[i + k].

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.

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[i + k] and A[i + 1]...A[i + k + 1] only differ by a small number of elements.