30412번 - 산책 나온 춘배

문제

춘배는 혼자 있는 것을 좋아한다. 오늘은 이안이가 춘배를 데리고 공원으로 산책을 나왔다. 공원에는 $N$개의 탑으로 이루어진 특이한 모양의 장식물이 있었다. 춘배는 탑에 올라가고 싶어했지만, 산책을 나온 다른 고양이들도 탑에 올라가 있었고 춘배는 근처에 다른 고양이가 있는 것이 싫었다.

그래서 춘배는 이안이에게 근처에 높이가 비슷한 탑이 없게 만들어달라고 했다. 춘배는 양옆에 있는 탑과의 높이의 차이가 모두 $X$ 이상이 되도록 하고 싶었다. 장식 양 끝에 있는 탑의 경우 한쪽만 고려하면 된다. 이안이는 새로운 탑을 만들면 제일 좋겠지만, 그 정도까지의 권한은 없어 높이를 조정하는 방법을 택하기로 했다.

이안이는 공원의 돌로 탑의 높이를 1ドル$씩 증가시킬 수 있다. 이안이는 밤이 되고 고양이가 모두 집에 간 다음 공사를 시작할 것이라 미리 계산을 해놓기로 했다. 어떤 탑을 골라 높이를 1ドル$ 증가시키는 것을 한 번의 시행이라 할 때 이안이가 춘배가 원하는 자리를 만들 수 있는 최소 시행 횟수를 구해보자. 이안이는 탑의 높이를 제한 없이 늘릴 수 있다.

입력

첫 줄에 탑의 개수 $N$과 춘배가 원하는 차이 $X$가 주어진다. $(2 \le N \le 10^5, 1\le X\le 10^9)$

둘째 줄에 탑의 높이 $A_1, A_2, \cdots , A_{N}$이 주어진다. $(1 \le A_i \le 10^9, 1\le i \le N)$

출력

한 줄에 춘배가 원하는 자리를 만들기 위해서 이안이가 시행해야 하는 최소 횟수를 출력한다. 춘배가 원하는 자리가 이미 있는 경우 시행을 하지 않아도 됨을 유의하라.

제한

힌트