Day 2: Sliding Window Mex

mediumsliding window

You are given an array of N integers. Your task is to calculate the MEX of each window of k elements, from left to right.
The MEX is the smallest non-negative integer that does not appear in the array.
For example, the MEX for [3, 1, 4, 3, 0, 5] is 2.

Input Format:

The first line contains two integers

n

and

k

: the number of elements and the size of the window. Followed by

n

integers

x_{1}, x_{2}, \dots, x_{n}

: the contents of the array.

Output Format:

Print n - k + 1 values: the MEX values for each window of size k.

Constraints:

1 \leq k \leq n \leq 2 \cdot 10^{5}

0 \leq x_{i} \leq 10^{9}

Examples:

Example 1:

Input:

10 10
0 1 2 3 4 5 6 7 8 9

Output:

Example 2:

Input:

2 2
0 1

Output:

Example 3:

Input:

4 2
0 1 1 0

Output:

2 0 2

Code

Loading Editor...