봄보슬라브는 방금 세탁물들을 꺼내서 옷장의 선반 위에 놓았다. 이제 상자 안에 n짝의 깨끗한 양말이 들어 있다.
i번째 양말의 색상은 회색의 색조(밝기)를 결정하는 음이 아닌 정수 c(i) 하나로 표현된다. c(i) 값이 클수록 양말이 더 밝아지며, c(i) = 0은 양말이 완전히 검은색임을 의미한다.
매일 아침 봄보슬라브는 상자 안에서 양말 두 짝을 꺼내 신고 저녁에는 빨래 바구니에 넣는다. 빨래 바구니를 세탁소로 가져가기 전까지 같은 양말을 두 번은 신지 않는다. 봄보슬라브는 패션 경찰을 두려워하기 때문에, 두 양말(i, j)의 회색 색조 차이(|c(i) - c(j)|)가 d를 초과하는 양말 쌍을 신지 않을 것이다.
봄보슬라브는 매우 바쁘고 시간을 최적화하려고 노력한다. 그가 매일 아침 양말 두 짝을 최적의 방법으로 고른다면, 더러운 빨래 바구니를 세탁소로 운반하는 주기를 얼마나 더 길게 할 수 있을까?
입력
첫 번째 입력 줄에 두 정수가 주어진다. 각각 양말의 개수 n (1 <= n <= 200000)과 양말 밝기의 최대 차이 d (0 <= d <= 10^9)이다.
다음 줄에는 정수 0 <= c(i) <= 10^9 가 공백을 구분으로 하여 주어진다.
출력
봄보슬라브가 세탁소에 가지 않고 주어진 조건대로 양말을 신을 수 있는 최대 일 수를 출력하시오.
clrmt 2년 전 2
봄보슬라브는 방금 세탁물들을 꺼내서 옷장의 선반 위에 놓았다. 이제 상자 안에 n짝의 깨끗한 양말이 들어 있다.
i번째 양말의 색상은 회색의 색조(밝기)를 결정하는 음이 아닌 정수 c(i) 하나로 표현된다. c(i) 값이 클수록 양말이 더 밝아지며, c(i) = 0은 양말이 완전히 검은색임을 의미한다.
매일 아침 봄보슬라브는 상자 안에서 양말 두 짝을 꺼내 신고 저녁에는 빨래 바구니에 넣는다. 빨래 바구니를 세탁소로 가져가기 전까지 같은 양말을 두 번은 신지 않는다. 봄보슬라브는 패션 경찰을 두려워하기 때문에, 두 양말(i, j)의 회색 색조 차이(|c(i) - c(j)|)가 d를 초과하는 양말 쌍을 신지 않을 것이다.
봄보슬라브는 매우 바쁘고 시간을 최적화하려고 노력한다. 그가 매일 아침 양말 두 짝을 최적의 방법으로 고른다면, 더러운 빨래 바구니를 세탁소로 운반하는 주기를 얼마나 더 길게 할 수 있을까?
입력
첫 번째 입력 줄에 두 정수가 주어진다. 각각 양말의 개수 n (1 <= n <= 200000)과 양말 밝기의 최대 차이 d (0 <= d <= 10^9)이다.
다음 줄에는 정수 0 <= c(i) <= 10^9 가 공백을 구분으로 하여 주어진다.
출력
봄보슬라브가 세탁소에 가지 않고 주어진 조건대로 양말을 신을 수 있는 최대 일 수를 출력하시오.
예제 입력 1
예제 출력 1
예제 입력 2
예제 출력 2