CSES - Datatähti Open 2017 - Mex value
  • Time limit: 1.00 s
  • Memory limit: 512 MB
The mex value of an array is the smallest nonnegative integer that doesn't appear in the array. For example, the mex value of the array $[3,0,4,3,7,1]$ is $2$.

Given an array of size $n$, your task is to calculate the mex value of each subarray of size $k$.

Input

The first input line contains numbers $n$ and $k$: the size of the array and the size of the subarray.

The next line contains $n$ numbers $x_1,x_2,\ldots,x_n$: the contents of the array.

Output

You should output $n-k+1$ numbers: the mex value of each subarray, in order from left to right.

Example

Input:
5 3
2 1 5 0 5


Output:
0 2 1

Explanation: The subarrays are $[2,1,5]$, $[1,5,0]$ and $[5,0,5]$.

Subtask 1 (28 points)
  • $1 \le k \le n \le 100$
  • $0 \le x_i \le 10^9$
Subtask 2 (72 points)
  • $1 \le k \le n \le 10^5$
  • $0 \le x_i \le 10^9$