D. Snowball
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Oh no! A graveyard has appeared and skeletons are attacking Ken's precious tower! More specifically, Ken is under siege for $$$k$$$ $$$(1 \leq k \leq 10^9)$$$ seconds facing a total of $$$n$$$ $$$(1 \leq n \leq 10^5)$$$ skeletons, where skeleton $$$i$$$ will spawn at time $$$a_i$$$. In order to try and defend his tower, Ken can use a powerful snowball, which kills all skeletons that have already spawned at once! However, Ken only has one snowball, so he must choose wisely when to use it!

At each second $$$x$$$ between $$$0 \dots k - 1$$$, the following occurs in order:

  • Any skeletons scheduled to spawn at time $$$x$$$ spawn in
  • If Ken uses his snowball at this time, the snowball is launched, instantly killing all alive skeletons
  • Each alive skeleton attacks Ken's tower, dealing 1 damage.

Help Ken find the minimum damage that his tower will take after the siege is over across all times at which he can use his snowball.

Input

The first line contains two integers, $$$n$$$ $$$(1 \leq n \leq 10^5)$$$ and $$$k$$$ $$$(1 \leq k \leq 10^9)$$$, where $$$n$$$ is the size of $$$a$$$ and $$$k$$$ is how long the siege lasts for.

The second line contains $$$n$$$ integers, $$$[a_1, a_2, ... a_n]$$$ $$$(0 \leq a_i \leq k - 1)$$$, the times at which each skeleton spawns

Output

Output one number, the minimum damage done to Ken's tower after the siege is over across all times at which he can use his snowball.

Examples
Input
2 3
0 1
Output
1
Input
4 10
0 9 9 9
Output
3
Note

In the first test case, if Ken uses the snowball at time $$$1$$$, both skeletons have spawned and are thus killed. In total, the skeleton that spawns at time $$$0$$$ does $$$1$$$ damage, and this is all.

In the second test case, if Ken uses the snowball at time $$$0$$$, the first skeleton is killed. The total damage is $$$3$$$, as $$$3$$$ more skeletons spawn in afterwards at time $$$9$$$, but they only have time for one attack before the siege ends.