시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 32 MB 11 7 7 63.636%

문제

OJ시는 직선 형태의 가로수길에 총 N개의 가로등을 설치했다. 각 가로등의 위치는 지하철역을 기준으로 -1,000,000,000 이상 1,000,000,000 이하의 정수로 나타낼 수 있다. 한편, 모든 가로등은 자신과 L만큼 먼 곳까지 빛을 밝힐 수 있다. 예를 들어, 좌표가 5인 가로등이 2만큼 먼 곳까지 빛을 밝힐 수 있다면 좌표가 3~7인 곳을 밝힐 수 있다.

요즘 들어, OJ시에 전력난이 지속되어 자주 정전이 난다. 정전이 나면 가로수길이 완전히 암흑에 둘러싸이기 때문에 치안에 악영향을 끼친다. 따라서 OJ시에서 N개의 가로등들 중 일부를 비상용으로 전환해서 정전 시에만 켜지게 할 것이다.

평소의 조명 상태와 정전 시의 조명 상태가 균일하게 이루어져야 언제든지 시민들이 편하게 가로수길을 드나들 수 있다. 이에 따라 OJ시는 어떤 경우에도 항상 빛이 도달하는 지점의 총 길이를 최대화시키려고 한다. OJ시를 도와 무슨 가로등을 비상용으로 바꿀지 구하는 프로그램을 작성하여라.

입력

첫 번째 줄에는 가로등의 수 N과 가로등의 조도 L이 주어진다.

두 번째 줄에는 N개의 가로등의 좌표가 공백을 사이로 두고 차례대로 주어진다.

  • 1 ≤ N ≤ 150,000
  • 1 ≤ L ≤ 1,000,000,000

출력

가로등 중에 몇 개를 비상용으로 전환했을 때, 평상시와 비상시에 모두 빛의 영향을 받는 영역의 길이의 최댓값을 출력한다.

 

예제 입력

6 3
-6 -2 1 3 8 15

예제 출력

9

힌트

2, 4번째 가로등을 비상용으로 전환하면 된다.