Lupa는 한 용기에서 다른 용기로 액체를 옮겨 붓는 것을 아주 좋아한다.

Lupa에게는 일반 투명 병 $n$개와 특별한 투명 병 하나가 있다. 각 일반 병의 높이는 $w$이다. 바닥의 높이는 $0$이고 꼭대기의 높이는 $w$이다. 특별한 병의 높이는 $2w$이다.

처음에는 모든 병에 주스가 동일한 숨겨진 정수 높이 $x$까지 채워져 있으며, $0\le x\le w$이다. Lupa는 $x$의 값을 모른다.

일반 병은 어두운 라벨로 일부가 가려져 있다. $i$번째 일반 병에서는 라벨이 높이 $l_i$부터 $w$까지를 모두 가린다. 따라서 이 병의 주스 높이가 $l_i$보다 엄격히 낮을 때, 그리고 그때에만 Lupa가 그 높이를 볼 수 있다.

특별한 병에는 다른 라벨이 붙어 있다. 이 라벨은 높이 $0$부터 $w$까지를 모두 가린다. 따라서 특별한 병의 주스 높이가 $w$보다 엄격히 높을 때, 그리고 그때에만 Lupa가 그 높이를 볼 수 있다.

Lupa는 숨겨진 값 $x$를 유일하게 알아내고 싶다.

Lupa는 주스를 부을 수 있다. 한 번 부을 때 일반 병 하나와 음이 아닌 정수 양 $p$를 선택하고, 이 일반 병에서 특별한 병으로 정확히 $p$ 단위의 주스를 붓는다. 매번 부은 뒤에는 위에서 설명한 라벨에 따라 볼 수 있는 모든 주스 높이를 관찰한다.

그러나 Lupa는 불가능할 수도 있는 붓기를 해서는 안 된다. 더 정확히 말하면, 붓기를 선택하기 전에 지금까지의 모든 관찰과 모순되지 않는 $x$의 모든 값을 고려한다. 선택한 병에서 $p$ 단위를 붓는 것은, 이러한 가능한 $x$의 모든 값에 대해 그 병에 적어도 $p$ 단위의 주스가 들어 있을 때에만 허용된다.

Lupa의 전략은 관찰에 따라 달라질 수 있다. 다음 붓기는 이전 붓기 이후에 얻은 관찰에 따라 결정해도 된다. 관찰만으로 $x$의 값이 유일하게 결정되는 즉시 멈춘다.

숨겨진 값 $x$가 무엇이든 $x$를 알아낼 수 있음을 보장하는 최소 붓기 횟수를 구하여라.

입력

첫째 줄에 두 정수 $n$과 $w$ ($1\le n\le 10^6$, $2\le w\le 10^{18}$)가 주어진다. 각각 일반 병의 개수와 높이이다.

둘째 줄에 $n$개의 정수 $l_1,l_2,\ldots,l_n$ ($1\le l_i<w$)이 주어진다. 각 일반 병의 어두운 라벨의 아래쪽 높이이다.

출력

$x$를 알아낼 수 있음을 보장하는 데 필요한 최소 붓기 횟수를 나타내는 정수 하나를 출력하여라.

예제

입력 1

3 34
1 2 4

출력 1

3

참고

첫 번째 테스트에서 라벨의 높이가 $4$인 병을 생각하자. $x<4$이면 주스를 붓기 전부터 그 높이를 볼 수 있으므로 이미 $x$를 알고 있다. 따라서 $4\le x\le34$라고 가정하자.

Lupa는 먼저 라벨의 높이가 $4$인 병에서 특별한 병으로 $4$ 단위의 주스를 붓는다.

이후 $x<8$이면 이 병의 주스 높이는 $x-4<4$이므로 볼 수 있고, $x$를 알아낼 수 있다. $x>30$이면 특별한 병의 주스 높이는 $x+4>34$이므로 볼 수 있고, $x$를 알아낼 수 있다. 따라서 여전히 알 수 없을 가능성이 있는 값은 $8\le x\le30$뿐이다.

다음으로 Lupa는 같은 병에서 $4$ 단위의 주스를 더 붓는다.

이후 $x<12$이면 이 병의 주스 높이는 $x-8<4$이므로 볼 수 있고, $x$를 알아낼 수 있다. $x>26$이면 특별한 병의 주스 높이는 $x+8>34$이므로 볼 수 있고, $x$를 알아낼 수 있다. 따라서 여전히 알 수 없을 가능성이 있는 값은 $12\le x\le26$뿐이다.

마지막으로 Lupa는 라벨의 높이가 $2$인 병에서 $12$ 단위의 주스를 붓는다.

이후 $x<14$이면 이 병의 주스 높이는 $x-12<2$이므로 볼 수 있고, $x$를 알아낼 수 있다. $x>14$이면 특별한 병의 주스 높이는 $x+20>34$이므로 볼 수 있고, $x$를 알아낼 수 있다. 남는 유일한 값은 $x=14$이므로 이 경우에도 값을 알아낼 수 있다.

따라서 주스를 3번 부은 뒤에는 Lupa가 반드시 $x$를 알아낼 수 있다.