Maximum Unique Integers in Subarrays

You are given an array of N integers and an integer k. Your task is to compute the number of unique integers in every contiguous subarray of length k.

For example, if N = 6, A = [4, 1, 1, 3, 1, 2], and k = 3, then the contiguous subarrays are:

• [4, 1, 1] with 2 unique integers,
• [1, 1, 3] with 2 unique integers,
• [1, 3, 1] with 2 unique integers,
• [3, 1, 2] with 3 unique integers.

The answer for this case is 2 2 2 3.

Note: In terms of mathematical notation, if we denote {@literal subarray} as \(S_i = [A_i, A_{i+1}, \dots, A_{i+k-1}]\) for \(1 \leq i \leq N-k+1\), then your task is to compute \(f(S_i)\) where \(f(S_i)\) is the number of distinct elements in \(S_i\).

inputFormat

The input is read from stdin and consists of:

1. A line containing a single integer N — the number of elements in the array.
2. A line with N space separated integers representing the array A.
3. A line containing a single integer k — the length of the subarray to consider.

outputFormat

Output to stdout a single line containing \(N-k+1\) integers separated by spaces, where each integer represents the number of unique elements in the corresponding subarray.

6
4 1 1 3 1 2
3

2 2 2 3