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