#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/7/problems/d

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/7/problems/d

Repovive

Maximum MEX - Repovive Career Starter Round 1 | Repovive | Repovive

Back

Code

Upload

Submissions

Learn

7D. Maximum MEX

2000 ptstype :zen to enter zen mode

by AmirMohammad Shahrezaei (AmShZ)

Time: 2sMemory: 256 MB

For a sequence of integers, its mex is the smallest non-negative integer that does not appear in the sequence.

For example, the mex of $[1,2,4]$ is $0$ , because $0$ does not appear in the sequence.

The mex of $[0,1,1,2,5]$ is $3$ , because $0$ , $1$ , and $2$ appear, but $3$ does not appear.

You are given an array $a_1, a_2, \ldots, a_n$ and an integer $k$ .

Your goal is to make the mex of the array as large as possible.

In one operation, you can choose an index $i$ and replace $a_i$ with $a_i + k$ .

You may perform this operation any number of times, possibly zero. You may also apply the operation to the same element more than once.

Find the maximum possible mex of the array.

Constraints

$1 \le n \le 2 \times 10^5$
$1 \le k \le n$
$0 \le a_i \le n$

Input

n \quad k

a_1 \quad a_2 \quad \cdots \quad a_n

Output

ans

Samples

Input

5 2
1 1 0 2 3

Explanation

The array already contains $0,1,2,3$ , so the mex is at least $4$ . Since there is no unused element that can become $4$ , the mex cannot be larger.

Output

Input

6 3
0 1 2 0 1 2

Explanation

The second copy of each of $0,1,2$ can be increased by $3$ . Then the array can contain all values from $0$ to $5$ .

Output

Input

5 3
2 2 2 2 2

Explanation

$0$ can never appear.

Output

For a sequence of integers, its mex is the smallest non-negative integer that does not appear in the sequence.

For example, the mex of $[1,2,4]$ is $0$ , because $0$ does not appear in the sequence.

The mex of $[0,1,1,2,5]$ is $3$ , because $0$ , $1$ , and $2$ appear, but $3$ does not appear.

You are given an array $a_1, a_2, \ldots, a_n$ and an integer $k$ .

Your goal is to make the mex of the array as large as possible.

In one operation, you can choose an index $i$ and replace $a_i$ with $a_i + k$ .

You may perform this operation any number of times, possibly zero. You may also apply the operation to the same element more than once.

Find the maximum possible mex of the array.

$1 \le n \le 2 \times 10^5$
$1 \le k \le n$
$0 \le a_i \le n$

n \quad k

a_1 \quad a_2 \quad \cdots \quad a_n

ans

The array already contains $0,1,2,3$ , so the mex is at least $4$ . Since there is no unused element that can become $4$ , the mex cannot be larger.

The second copy of each of $0,1,2$ can be increased by $3$ . Then the array can contain all values from $0$ to $5$ .