Hide

Problem J
Perfect Porridge

As a true student Lucky Luke eats a big bowl of perfect porridge each morning. Luke’s goal in life is to get every chalmerist to love porridge.

In the faculty there are $N$ yet-to-be-enlightened students. Luke is unfortunately not necessarily able to serve perfect porridge to all of them. But he will do his best and try to serve as many of them as possible. He starts to microwave the water and oat mixture at $t=0$, one portion at a time with each requiring $2$ minutes of microwaving in the sole available microwave oven on campus. A man of great manners, Luke will serve the chosen subset of students all at once.

There are two complications: first, porridge will go cold after staying out in the open for $M$ minutes, requiring $1$ minute of re-heating. Second, the entitled brats care more about their exams than porridge and will leave the table when they grow impatient. Student $i$ has an associated impatience $I_ i$, the time after which they will leave the table.

Porridge that is done at time $t$ will be cold at time $t+M$ but not at time $t+M-1$. Luke can schedule cooking and re-heating however he wants. For example, he is allowed to do the following: cooking, cooking, re-heating, cooking, re-heating, all in the span of $8$ minutes. A student with impatience $I_ i$ will still be at the table at time $I_ i$, but not at time $I_ i+1$. Luke must not necessarily serve all seated students at the time of serving.

Input

The first line of input contains two integers $N$, $1 \leq N \leq 500\, 000$, the number of students and $M$, $1 \leq M \leq 10^9$, the number of minutes it takes for warm porridge to get cold. The second line contains the $N$ integers $I_0, I_1 \ldots I_{N-1}$, where $I_ i$, $1 \leq I_ i \leq 10^9$, denotes the impatience of student $i$.

Output

Output a single integer, the maximal number of students that Lucky Luke can convince to love porridge.

Sample Input 1 Sample Output 1
3 100
1 4 4
2
Sample Input 2 Sample Output 2
4 5
8 9 8 9
3
Sample Input 3 Sample Output 3
8 6
99 104 97 108 109 101 114 115
6
Sample Input 4 Sample Output 4
10 3
1 2 3 4 5 6 7 8 9 10
3

Please log in to submit a solution to this problem

Log in