Maximum MEX - Repovive Starter Round 1 | Repovive

7D. Maximum MEX

2000 pts2s256 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$ .

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

7D. Maximum MEX

Constraints

Input

Output

Samples

7D. Maximum MEX

Constraints

Input

Output

Samples