N 마리의 코끼리가 무대에서 한 줄로 서서 춤을 추는 코끼리 쇼는 파타야에서는 매우 유명하다.

몇 년간의 훈련후, 코끼리들은 이 쇼에서 많은 놀랄만한 춤들을 출 수 있게 된다. 이 쇼는 일련의 동작으로 이루어진다. 각 동작에서는, 정확히 한 코끼리만 다른 장소로 이동하는 귀여운 춤을 추는데, 제자리에 있을 수도 있다.

쇼 제작자는 전체 쇼의 사진을 포함하는 사진첩을 제작하려 한다. 각 동작마다, 관객들에게 보여지는 모든 코끼리들의 사진을 찍으려고 한다. 쇼가 진행되는 동안, 여러 마리의 코끼리들은 같은 장소에 있을 수 있다. 이 경우, 같은 장소에 있는 코끼리들은 단순히 다른 코끼리의 뒤에 서 있게 된다.

하나의 카메라는 길이 L 의 선분상에 있는 코끼리들의 사진만 찍을 수 있다(양 끝점 포함). 코끼리들은 무대 전체에 흩어져 있을 수 있으므로, 모든 코끼리들에 대한 동시의 스냅사진을 찍기 위해서는 여러 대의 카메라가 필요할 수도 있다.

예를 들어, L=10 이고 무대에서 코끼리들의 위치가 10, 15, 17, 그리고 20 이라고 하자. 이 순간에는, 아래의 그림과 같이, 하나의 카메라로 모든 코끼리들의 사진을 찍을 수 있다. (삼각형은 코끼리를 나타내고; 사다리꼴은 카메라를 나타낸다.)

그 다음의 동작에서는 15 에 있던 코끼리가 32 의 위치로 춤추며 이동한다. 이 동작 후의 스냅 사진을 찍기 위해서는 적어도 두 대의 카메라가 필요하다.

그 다음의 동작에서 10 에 있던 코끼리가 7 의 위치로 이동한다. 이 경우에서는 모든 코끼리들의 사진을 찍기 위해서 세대의 카메라가 필요하다.

이 상호작용 태스크에서는, 각 코끼리들의 동작 후의 코끼리 사을 찍기 위한 최소 수의 카메라를 찾아야 한다. 매 동작마다 카메라의 수는 증가할 수도 있고, 감소할 수도 있으며, 변화가 없을 수도 있음에 주의하라.

제한시간은 9 초이다.

입력

• N - 코끼리의 수. 코끼리는 0 이상 N-1 이하의 번호로 나타낸다.1 ≤ N ≤ 150 000.
• L - 하나의 카메라로 찍을 수 있는 선분의 길이. L 은 정수이며, 0 ≤ L ≤ 1 000 000 000 이다.
• X - 코끼리들의 처음 위치를 나타내는 하나의 일차원 정수 배열. 0 ≤ i < N 에 대하여, 코끼리 i 의 초기위치는 X[i]이고, 정렬이 되어있다. 좀 더 정확하게 말하자면, 0 ≤ X[0] ≤ ... ≤ X[N-1] ≤ 1 000 000 000 이다. 코끼리들의 춤(동작) 후에 위치가 재 배열 될 수 있음에 주의하라.최대 150 000 이고 여러마리의 코끼리 들이 같은 위치에 있을수 있다.

출력

입출력 예

입력

4 10 5
10
15
17
20
2 16
1 25
3 35
0 38
2 0 

출력

1
2
2
2
3

출처:ioi 2011 day2 2/3