Lupa is a big fan of transfusing some liquid from one container to another.

Lupa has $n$ ordinary transparent bottles and one special transparent bottle. Each ordinary bottle has height $w$: its bottom is at level $0$, and its top is at level $w$. The special bottle has height $2w$.

All bottles are initially filled with juice up to the same hidden integer level $x$, where $0 \le x \le w$. Lupa does not know the value of $x$.

The ordinary bottles are partially covered by dark labels. In the $i$-th ordinary bottle, the label covers all levels from $l_i$ to $w$. Therefore, the juice level in this bottle is visible to Lupa if and only if it is strictly below $l_i$.

The special bottle has a different label: it covers all levels from $0$ to $w$. Therefore, the juice level in the special bottle is visible to Lupa if and only if it is strictly above $w$.

Lupa wants to determine the hidden value $x$ uniquely.

Lupa may perform pours. In one pour, she chooses one of the ordinary bottles and a non-negative integer amount $p$, then pours exactly $p$ units of juice from this ordinary bottle into the special bottle. After each pour, Lupa observes all juice levels that are visible, according to the labels described above.

However, Lupa is not allowed to make a pour that might be impossible. More precisely, before choosing a pour, consider all values of $x$ that are still consistent with every observation made so far. The pour of $p$ units from the chosen bottle is allowed only if, for every such possible value of $x$, that bottle contains at least $p$ units of juice.

Lupa’s strategy may be adaptive: the next pour may depend on the observations obtained after the previous pours. She stops as soon as the observations uniquely determine the value of $x$.

Find the minimum number of pours that guarantees determining $x$, no matter what the hidden value $x$ is.

Input

The first line contains two integers $n$ and $w$ ($1 \le n \le 10^6$, $2 \le w \le 10^{18}$) — the number of ordinary bottles and their height.

The second line contains $n$ integers $l_1, l_2, \ldots, l_n$ ($1 \le l_i < w$) — the lower levels of the dark labels on the ordinary bottles.

Output

Output one integer — the minimum number of pours required to guarantee determining $x$.

Examples

Input 1

3 34
1 2 4

Output 1

3

Note

In the first test, consider the bottle with label $4$. If $x < 4$, its juice level is visible before any pour, so $x$ is already known. Therefore, assume that $4 \le x \le 34$.

Lupa first pours $4$ units from the bottle with label $4$ into the special bottle.

After this pour, if $x < 8$, then the level in this bottle is $x - 4 < 4$, so it is visible and determines $x$. If $x > 30$, then the level in the special bottle is $x + 4 > 34$, so it is visible and determines $x$. Therefore, only values $8 \le x \le 30$ may still be unknown.

Next, Lupa pours $4$ more units from the same bottle.

After this pour, if $x < 12$, then the level in this bottle is $x - 8 < 4$, so it is visible and determines $x$. If $x > 26$, then the level in the special bottle is $x + 8 > 34$, so it is visible and determines $x$. Therefore, only values $12 \le x \le 26$ may still be unknown.

Finally, Lupa pours $12$ units from the bottle with label $2$.

After this pour, if $x < 14$, then the level in this bottle is $x - 12 < 2$, so it is visible and determines $x$. If $x > 14$, then the level in the special bottle is $x + 20 > 34$, so it is visible and determines $x$. The only remaining value is $x = 14$, so it is also determined.

Thus, after $3$ pours, Lupa is guaranteed to determine $x$.