Mishka received a gift of multicolored pencils for his birthday! Unfortunately he lives in a monochrome world, where everything is of the same color and only saturation differs. This pack can be represented as a sequence a_1, a_2, ..., a_{n} of n integer numbers — saturation of the color of each pencil. Now Mishka wants to put all the mess in the pack in order. He has an infinite number of empty boxes to do this. He would like to fill some boxes in such a way that:

  Each pencil belongs to exactly one box;  Each non-empty box has at least k pencils in it;  If pencils i and j belong to the same box, then |a_{i} - a_{j}| ≤ d, where |x| means absolute value of x. Note that the opposite is optional, there can be pencils i and j such that |a_{i} - a_{j}| ≤ d and they belong to different boxes. 

Help Mishka to determine if it's possible to distribute all the pencils into boxes. Print "YES" if there exists such a distribution. Otherwise print "NO".


-----Input-----

The first line contains three integer numbers n, k and d (1 ≤ k ≤ n ≤ 5·10^5, 0 ≤ d ≤ 10^9) — the number of pencils, minimal size of any non-empty box and maximal difference in saturation between any pair of pencils in the same box, respectively.

The second line contains n integer numbers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9) — saturation of color of each pencil.


-----Output-----

Print "YES" if it's possible to distribute all the pencils into boxes and satisfy all the conditions. Otherwise print "NO".


-----Examples-----
Input
6 3 10
7 2 7 7 4 2

Output
YES

Input
6 2 3
4 5 3 13 4 10

Output
YES

Input
3 2 5
10 16 22

Output
NO



-----Note-----

In the first example it is possible to distribute pencils into 2 boxes with 3 pencils in each with any distribution. And you also can put all the pencils into the same box, difference of any pair in it won't exceed 10.

In the second example you can split pencils of saturations [4, 5, 3, 4] into 2 boxes of size 2 and put the remaining ones into another box.

Difficulty: interview

Starter code:

Solutions:
#!/usr/bin/env python3

from bisect import bisect

[n, k, d] = list(map(int, input().strip().split()))
ais = list(map(int, input().strip().split()))
if k == 1:
	print ('YES')
	return

ais.sort()

# can do ais[i:]
cando = [False for _ in range(n)]
j = n - 1  # j is such that a[j] > a[i] + d >= a[j - 1]  (upper_bound) a[:j] <= a[i] + d < a[j:]
count = 0  # sum(cando[i + k:j + 1])
for i in reversed(list(range(n))):
	if i + k < n and cando[i + k]:
		count += 1
	if n - i < k:
		continue
	if ais[-1] - ais[i] <= d:
		cando[i] = True
		continue
	while ais[j - 1] > ais[i] + d:
		if cando[j]:
			count -= 1
		j -= 1
	cando[i] = (count > 0)
	

if cando[0]:
	print ('YES')
else:
	print ('NO')



from bisect import bisect_right, bisect_left


def main():
    n, k, d = map(int, input().split())
    sat = [int(x) for x in input().split()]

    sat = sorted(sat)
    arrange = [False for _ in range(n + 1)]
    arrange[0] = True
    s = 0
    # i means the first i items could be arranged well
    i = min(bisect_right(sat, sat[s] + d), k)
    n_arrange = 1 if i - k >= 0 else 0 # arrange[0] == True | the first 0 items

    while i <= n:
        if i - s >= k and n_arrange > 0:
            arrange[i] = True
        if i < n:
            news = bisect_left(sat, sat[i] - d, s, i)
            while s < news:
                if s <= i - k and arrange[s]:
                    n_arrange -= 1
                s += 1

        i += 1
        n_arrange += 1 if (i - k >= s and arrange[i - k]) else 0

    if arrange[n]:
        print('YES')
    else:
        print('NO')


def __starting_point():
    main()
__starting_point()

from bisect import bisect_right, bisect_left


def main():
    n, k, d = list(map(int, input().split()))
    sat = [int(x) for x in input().split()]

    sat = sorted(sat)

    # arrange[i] means the first i items could be arranged well
    # arranged well means they could be put into boxes without conflicts
    arrange = [True] + [False for _ in range(n)]

    s = 0

    # we can put [0, i) items into the first box
    i = min(bisect_right(sat, sat[s] + d), k)

    # keep the number of True-value in arrange[s, i-k]
    # there must be at least one point in [s, i-k(included)] which satisfies arrange[this_point] == True
    # that means we can cut from this_point and put [this_point, i) in a new box
    # then the result is arrange[i] become True, because now all items before i-index could be arranged well
    n_arrange = 1 if s <= i - k else 0

    while i <= n:
        if i - s >= k and n_arrange > 0:
            arrange[i] = True
        if i < n:
            # find new s that we could put | item at new s - item at i | <= d
            news = bisect_left(sat, sat[i] - d, s, i)
            while s < news:
                if s <= i - k and arrange[s]:
                    n_arrange -= 1
                s += 1

        i += 1
        # every time when you count arrange[x] you should keep x between [s, i-k]
        n_arrange += 1 if (s <= i - k and arrange[i - k]) else 0

    if arrange[n]:
        print('YES')
    else:
        print('NO')


def __starting_point():
    main()

__starting_point()

import bisect;
def getIntList():
    return list(map(int, input().split()));
def getTransIntList(n):
    first=getIntList();
    m=len(first);
    result=[[0]*n for _ in range(m)];
    for i in range(m):
        result[i][0]=first[i];
    for j in range(1, n):
        curr=getIntList();
        for i in range(m):
            result[i][j]=curr[i];
    return result;
n, k, d = getIntList()
a= getIntList();
a.sort();
seen=[False]*len(a);
def search(a, lowLim):
    sameLim=bisect.bisect_right(a, a[lowLim]+d);
    lowLim=max(lowLim, sameLim-2*k);
    if seen[lowLim]:
        return False;
    if len(a)-lowLim<k:
        return False;
    if a[len(a)-1]-a[lowLim]<=d:
        return True;
    for i in range(lowLim+k-1, len(a)-1):
        if a[i]-a[lowLim]>d:
            break;
        if search(a, i+1):
            return True;
    seen[lowLim]=True;
    return False;
def searchFull(a):
    if a[n-1]-a[n-k]>d:
        return False;
    return search(a, 0);
if k==1:
    print('YES')
elif searchFull(a):
    print('YES')
else:
    print('NO');

import bisect;
def getIntList():
    return list(map(int, input().split()));
def getTransIntList(n):
    first=getIntList();
    m=len(first);
    result=[[0]*n for _ in range(m)];
    for i in range(m):
        result[i][0]=first[i];
    for j in range(1, n):
        curr=getIntList();
        for i in range(m):
            result[i][j]=curr[i];
    return result;
n, k, d = getIntList()
a= getIntList();
a.sort();
#Возможно разрезать отрезок до j не включительно - cuttable[j];
cuttable=[False]*len(a);
cuttable[0]=True;
def search(a):
    curr=0;
    maxOne=0;
    while True:
        #print(curr);
        if cuttable[curr]:
            #Добавляем одрезок длины как минимум k: [curr, curr+k)
            lowLim=curr+k;
            #Находим первый такой индекс upLim, что a[upLim]-a[curr]>d;
            upLim=bisect.bisect_right(a, a[curr]+d);
            #Если такого элемента нет, решение найдено
            if upLim==len(a):
                return True;
            #Ставить единички на уже пройденый отрезок бессмысленно
            lowLim=max(lowLim, maxOne+1);
            #print('cuttable', lowLim, upLim);
            #a[upLim-1]-a[curr]<=d, значит cuttable[upLim]=True;
            for i in range(lowLim, upLim+1):
                cuttable[i]=True;
            maxOne=upLim;
        curr+=1;
        if curr>len(a)-k:
            break;
    return False;
if k==1:
    print('YES')
elif search(a):
    print('YES')
else:
    print('NO');

def getIntList():
    return list(map(int, input().split()));
def getTransIntList(n):
    first=getIntList();
    m=len(first);
    result=[[0]*n for _ in range(m)];
    for i in range(m):
        result[i][0]=first[i];
    for j in range(1, n):
        curr=getIntList();
        for i in range(m):
            result[i][j]=curr[i];
    return result;
n, k, d = getIntList()
a= getIntList();
a.sort();
#Возможно разрезать отрезок до j не включительно - cuttable[j];
cuttable=[False]*len(a);
cuttable[0]=True;
def search(a):
    curr=0;
    upLim=0;
    upLimPrev=0;
    while True:
        #print(curr);
        if cuttable[curr]:
            #Добавляем одрезок длины как минимум k: [curr, curr+k)
            lowLim=curr+k;
            upLimPrev = upLim;
            #Находим первый такой индекс upLim, что a[upLim]-a[curr]>d;
            while upLim<len(a) and a[upLim]-a[curr]<=d:
                upLim+=1;
            #Если такого элемента нет, решение найдено
            if upLim==len(a):
                return True;
            #Ставить единички на уже пройденый отрезок бессмысленно
            lowLim=max(lowLim, upLimPrev+1);
            #print('cuttable', lowLim, upLim);
            #a[upLim-1]-a[curr]<=d, значит cuttable[upLim]=True;
            for i in range(lowLim, upLim+1):
                cuttable[i]=True;
        curr+=1;
        if curr>len(a)-k:
            break;
    return False;
if k==1:
    print('YES')
elif search(a):
    print('YES')
else:
    print('NO');

from bisect import bisect


def main():
    n, k, d = list(map(int, input().split()))
    if k == 1:
        print('YES')
        return
    l = []
    ll = [l]
    a = 10 ** 10
    for b in sorted(map(int, input().split())):
        if a < b:
            if len(l) < k:
                print('NO')
                return
            l = [b]
            ll.append(l)
        else:
            l.append(b)
        a = b + d

    def f(a):
        def dfs(i):
            avail[i] = False
            if i + k <= le:
                if a[-1] <= a[i] + d:
                    raise TabError
                j = bisect(a, a[i] + d, i, -1) - 1
                for j in range(bisect(a, a[i] + d, i, -1), i + k - 1, -1):
                    if avail[j]:
                        dfs(j)

        le = len(a)
        avail = [True] * le
        try:
            dfs(0)
        except TabError:
            return True
        return False

    print(('NO', 'YES')[all(map(f, ll))])


def __starting_point():
    main()

__starting_point()

n, k, d = list(map(int, input().split()))
a = sorted(list(map(int, input().split())))
b = [0] * n
i = j = 0
for i in range(n):
    while a[i] - a[j] > d:
        j += 1
    b[i] = j
c = [0] * n
# d = [0] * n
for i in range(k - 1, n):
    # print(f'i={i}, b[i]={b[i]}, i-b[i]+1={i - b[i] + 1}, i-k={i-k}, c[i-k]={c[i-k]}, c[b[i]]={c[b[i]]}')
    # print(i - k, b[i] - 2)
    if i - b[i] + 1 >= k and (b[i] == 0 or c[i - k] > c[b[i] - 2] or (b[i] == 1 and c[i-k]> c[0])):
        c[i] = c[i - 1] + 1
        # d[i] = 1
    else:
        c[i] = c[i - 1]
# print(a)
# print(b)
# print(d)
# print(c)
print('YES' if n < 2 or c[n - 1] > c[n - 2] else 'NO')

n, k, d = list(map(int, input().split()))
a = sorted(list(map(int, input().split())))
b = [0] * n
i = j = 0
for i in range(n):
    while a[i] - a[j] > d:
        j += 1
    b[i] = j
c = [0] * n
for i in range(k - 1, n):
    c[i] = c[i - 1] + int(i - b[i] + 1 >= k and (b[i] == 0 or c[i - k] > c[b[i] - 2] or (b[i] == 1 and c[i-k]> c[0])))
print('YES' if n < 2 or c[n - 1] > c[n - 2] else 'NO')

n,k,d=list(map(int,input().split()))
a=sorted(list(map(int,input().split())))
b=[0]*n
i=j=0
for i in range(n):
    while a[i]-a[j]>d:j+=1
    b[i]=j
c=[0]*n
for i in range(k-1,n):c[i]=c[i-1]+int(i-b[i]+1>=k and (b[i]==0 or c[i-k]>c[b[i]-2] or (b[i]==1 and c[i-k]>c[0])))
print('YES' if n<2 or c[n-1]>c[n-2] else 'NO')

#Bhargey Mehta (Junior)
#DA-IICT, Gandhinagar
import sys, math, queue
#sys.stdin = open('input.txt', 'r')
MOD = 998244353
sys.setrecursionlimit(1000000)

def check(i):
    if not dp[i][2]: return False
    if i < 0: return True
    return check(i-dp[i][1])
 
n, k, d = map(int, input().split())
if k == 1:
    print('YES')
    return
a = sorted(map(int, input().split()))
dp = [None for i in range(n)]
dp[0] = (a[0], 1, False)
for i in range(1, n):
    if a[i]-dp[i-1][0] <= d:
        dp[i] = (dp[i-1][0], dp[i-1][1]+1, dp[i-1][1]+1 >= k)
    else:
        dp[i] = (a[i], 1, False)
        j = i
        while a[i]-a[j] <= d and j > 0:
            j -= 1
            if dp[j][2]:
                dp[i] = (a[j+1], i-j, i-j >= k)
            if dp[i][2]: break
print('YES' if check(n-1) else 'NO')

def bi_search(a, x):
    n = len(a)
    u, l = n, -1
    
    while u-l>1:
        md=(u+l)//2
        
        if x>a[md]:
            l=md
        else:
            u=md
    
    return u 

class Bit():
    # index-1
    def __init__(self, n):
        self.bit = [0] * (n+1) 
        self.n   = n
    
    # sum[1, i]
    def sum_prefix(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i&(-i)
        return s
        
    # sum[l, r]    
    def sum_(self, l, r):
        if l == 1:
            return self.sum_prefix(r)
        return self.sum_prefix(r) - self.sum_prefix(l-1) 
        
    def add(self, i, x):
        while i <= self.n:
            self.bit[i] += x
            i += i&(-i)

n, k, d = map(int, input().split())
a = [-1] + list(map(int, input().split()))
a = sorted(a)

B=Bit(n) 
ans=[-1] * n 

for i in range(n+1):
    if i==0:
        continue
        
    pos  = bi_search(a, max(0, a[i]-d)) #pos,   i-k+1..,i-1,i
    
    l, r = pos-1, i-k
    
    if l<=r:
        s=0
        
        if l>=1:
            s+=B.sum_(l, r)
        
        if l==0 or s > 0:
            B.add(i, 1)
            ans[i-1]=1
            
if ans[-1]==1:
    print('YES')
else:
    print('NO')

def main():
    import sys
    from bisect import bisect_left
    input = sys.stdin.readline

    N, K, D = list(map(int, input().split()))
    A = list(map(int, input().split()))
    A.sort()

    part = [0] * (N+2)
    part[0] = 1
    part[1] = -1
    for i, a in enumerate(A):
        part[i] += part[i-1]
        if part[i]:
            j = bisect_left(A, a+D+1)
            if j >= i+K:
                part[i+K] += 1
                part[j+1] -= 1
    part[N] += part[N-1]
    if part[N]:
        print('YES')
    else:
        print('NO')
    #print(A)
    #print(part)


def __starting_point():
    main()

__starting_point()

import bisect
import sys
input = sys.stdin.readline


class SegmentTree():
    def __init__(self, n, op, e):
        self.n = n
        self.op = op
        self.e = e
        self.size = 2 ** ((n - 1).bit_length())
        self.node = [self.e] * (2 * self.size)

    def built(self, array):
        for i in range(self.n):
            self.node[self.size + i] = array[i]
        for i in range(self.size - 1, 0, -1):
            self.node[i] = self.op(self.node[i << 1], self.node[(i << 1) + 1])

    def update(self, i, val):
        i += self.size
        self.node[i] = val
        while i > 1:
            i >>= 1
            self.node[i] = self.op(self.node[i << 1], self.node[(i << 1) + 1])

    def get_val(self, l, r):
        l, r = l + self.size, r + self.size
        res_l, res_r = self.e, self.e
        while l < r:
            if l & 1:
                res_l = self.op(res_l, self.node[l])
                l += 1
            if r & 1:
                r -= 1
                res_r = self.op(self.node[r], res_r)
            l, r = l >> 1, r >> 1
        return self.op(res_l, res_r)


n, k, d = map(int, input().split())
a = list(map(int, input().split()))
a = sorted(a)

st = SegmentTree(n + 1, lambda a, b : a | b, 0)
st.update(0, 1)
for i in range(n):
    tmp = bisect.bisect_left(a, a[i] - d)
    if tmp >= max(i + 2 - k, 0):
        continue
    st.update(i + 1, st.get_val(tmp, max(i + 2 - k, 0)))

if st.get_val(n, n + 1) == 1:
    print("YES")
else:
    print("NO")

import sys
readline = sys.stdin.readline

class Segtree:
    def __init__(self, A, intv, initialize = True, segf = max):
        self.N = len(A)
        self.N0 = 2**(self.N-1).bit_length()
        self.intv = intv
        self.segf = segf
        if initialize:
            self.data = [intv]*self.N0 + A + [intv]*(self.N0 - self.N)
            for i in range(self.N0-1, 0, -1):
                self.data[i] = self.segf(self.data[2*i], self.data[2*i+1]) 
        else:
            self.data = [intv]*(2*self.N0)
        
    def update(self, k, x):
        k += self.N0
        self.data[k] = x
        while k > 0 :
            k = k >> 1
            self.data[k] = self.segf(self.data[2*k], self.data[2*k+1])
    
    def query(self, l, r):
        L, R = l+self.N0, r+self.N0
        s = self.intv
        while L < R:
            if R & 1:
                R -= 1
                s = self.segf(s, self.data[R])
            if L & 1:
                s = self.segf(s, self.data[L])
                L += 1
            L >>= 1
            R >>= 1
        return s
    
    def binsearch(self, l, r, check, reverse = False):
        L, R = l+self.N0, r+self.N0
        SL, SR = [], []
        while L < R:
            if R & 1:
                R -= 1
                SR.append(R)
            if L & 1:
                SL.append(L)
                L += 1
            L >>= 1
            R >>= 1
        
        if reverse:
            for idx in (SR + SL[::-1]):
                if check(self.data[idx]):
                    break
            else:
                return -1
            while idx < self.N0:
                if check(self.data[2*idx+1]):
                    idx = 2*idx + 1
                else:
                    idx = 2*idx
            return idx - self.N0
        else:
            for idx in (SL + SR[::-1]):
                if check(self.data[idx]):
                    break
            else:
                return -1
            while idx < self.N0:
                if check(self.data[2*idx]):
                    idx = 2*idx
                else:
                    idx = 2*idx + 1
            return idx - self.N0

N, K, D = list(map(int, readline().split()))
A = list(map(int, readline().split()))
A.sort()
lm = [None]*N
for i in range(N):
    a = A[i]
    ok = i
    ng = -1
    while abs(ok-ng) > 1:
        med = (ok+ng)//2
        if a-A[med] <= D:
            ok = med
        else:
            ng = med
    lm[i] = ok

T = Segtree([None]*(N+1), 0, initialize = False, segf = max)
T.update(0, 1)
for i in range(N):
    rm = i-K+2
    if rm <= lm[i]:
        continue
    if T.query(lm[i], rm):
        T.update(i+1, 1)

print('YES' if T.query(N, N+1) else 'NO')



import heapq

def run():
    n, k, d = list(map(int, input().split()))
    a = sorted(map(int, input().split()))

    max_size = [None] * n  # how many pencils can be in box starting with this one
    start = 0
    end = 0
    while start < n:
        while end < n-1 and a[end+1] - a[start] <= d:
            end += 1
        max_size[start] = end - start + 1
        start += 1

    possilbe_starts = []
    # heap with starts and stops of intervals where new box can start
    # - all pencils before that are successfully boxed
    heapq.heappush(possilbe_starts, (0, "start"))
    heapq.heappush(possilbe_starts, (1, "stop"))

    number_of_opened = 0  # number of opened intervals

    for pencil in range(n):
        while possilbe_starts and possilbe_starts[0][0] <= pencil:
            top = heapq.heappop(possilbe_starts)
            number_of_opened += (1 if top[1] == "start" else -1)
        if number_of_opened <= 0:
            continue
        if max_size[pencil] < k:
            continue
        if pencil + max_size[pencil] + 1 > n:
            print("YES")
            break
        heapq.heappush(possilbe_starts, (pencil + k, "start"))
        heapq.heappush(possilbe_starts, (pencil + max_size[pencil] + 1, "stop"))
    else:
        print("NO")

run()


import sys

n, k, d = list(map(int, input().split()))
a = [0] + sorted(map(int, input().split()))
dp = [1] + [0]*n
j = k

for i in range(n):
    if dp[i] == 0:
        continue
    j = max(j, i+k)
    while j <= n and a[j] - a[i+1] <= d:
        dp[j] |= dp[i]
        j += 1

print('YES' if dp[-1] else 'NO')