There is a toy building consisting of $n$ towers. Each tower consists of several cubes standing on each other. The $i$-th tower consists of $h_i$ cubes, so it has height $h_i$.

Let's define operation slice on some height $H$ as following: for each tower $i$, if its height is greater than $H$, then remove some top cubes to make tower's height equal to $H$. Cost of one "slice" equals to the total number of removed cubes from all towers.

Let's name slice as good one if its cost is lower or equal to $k$ ($k \ge n$).

 [Image] 

Calculate the minimum number of good slices you have to do to make all towers have the same height. Of course, it is always possible to make it so.


-----Input-----

The first line contains two integers $n$ and $k$ ($1 \le n \le 2 \cdot 10^5$, $n \le k \le 10^9$) — the number of towers and the restriction on slices, respectively.

The second line contains $n$ space separated integers $h_1, h_2, \dots, h_n$ ($1 \le h_i \le 2 \cdot 10^5$) — the initial heights of towers.


-----Output-----

Print one integer — the minimum number of good slices you have to do to make all towers have the same heigth.


-----Examples-----
Input
5 5
3 1 2 2 4

Output
2

Input
4 5
2 3 4 5

Output
2



-----Note-----

In the first example it's optimal to make $2$ slices. The first slice is on height $2$ (its cost is $3$), and the second one is on height $1$ (its cost is $4$).

Difficulty: interview

Starter code:

Solutions:
def ii():
    return int(input())
def mi():
    return list(map(int, input().split()))
def li():
    return list(mi())

n, k = mi()
h = li()
m = max(h)
f = [0] * (m + 1)
for hi in h:
    f[hi] += 1
for i in range(m - 1, 0, -1):
    f[i] += f[i + 1]

ans = 0
i = m
while i > 0:
    if f[i] == n:
        break
    j = i
    cur = 0
    while j > 0:
        if cur + f[j] > k:
            break
        cur += f[j]
        j -= 1
    ans += 1
    i = j
print(ans)


import sys
import os

def solve(n, k, h):
    h.sort()
    top = h[len(h) - 1]

    s = [n] * top
    c = 0
    for i in range(top):
        s[i] = n - c
        while c < n and h[c] == i + 1:
            c += 1

    pack = 0
    result = 0
    c = top - 1
    while s[c] < n:
        diff = s[c]
        c -= 1

        if pack + diff <= k:
            pack += diff
        else:
            pack = diff
            result += 1

    if pack > 0:
        result += 1

    return result



def main():
    n, k = (int(x) for x in input().split())
    h = list(int(x) for x in input().split())
    print(solve(n, k, h))

def __starting_point():
    main()
__starting_point()

n, k = list(map(int, input().split()))
h = list(map(int, input().split()))

hs = {}

mx = 0
mn = 10**6
for a in h:
    mx = max(mx, a)
    mn = min(mn, a)
    if a not in hs:
        hs[a] = 0
    hs[a] += 1
ans = 0
cur = 0
curcl = 0
for i in range(mx, mn, -1):
    if i not in hs:
        nc = 0
    else:
        nc = hs[i]
    if cur + nc + curcl <= k:
        cur += nc + curcl
        curcl += nc
    else:
        ans +=1
        curcl += nc
        cur = curcl
if cur > 0:
    ans += 1
print(ans)


n, k = [int(i) for i in input().split()]
h = [int(i) for i in input().split()]
h.sort()
hh = h[0]
for i in range(len(h)):
    h[i] -= hh
g = [0] * h[-1]
last = 0
for i in range(1, len(h)):
    if h[i] > h[i-1]:
        for j in range(last, h[i]):
            g[j] = n - i
            last = h[i]
g.reverse()
s = 0
ans = 0
for i in range(len(g)):
    if s + g[i] > k:
        ans += 1
        s = g[i]
    else:
        s += g[i]
if s > 0:
    ans += 1
print(ans)


n,k = list(map(int,input().split()))
hhh = list(map(int,input().split()))

h = [0] *200005
hp = [0] * 200005

mx = 0
for i in hhh:
    h[i] +=1
    mx = max(mx,i)

res = n
for j in range(200003):
    hp[j] = res
    res -= h[j]


ans = 0
rr = 0
for t in range(mx,0,-1):
    if hp[t] == n:
        break

    rr += hp[t]
    if rr > k:
        rr = hp[t]
        ans += 1



if rr:
    ans += 1

print(ans)




from sys import stdin
n,m=list(map(int,stdin.readline().strip().split()))
s=tuple(map(int,stdin.readline().strip().split()))
ma=max(s)
mi=min(s)
dp=[0 for i in range(ma+3)]
for i in s:
    dp[i]+=1
for i in range(len(dp)-2,-1,-1):
    dp[i]+=dp[i+1]
x=0
ans=0
acum=0
l=-1
for i in range(len(dp)-2,mi-1,-1):
    dp[i]+=dp[i+1]
    if dp[i]-acum>m:
        acum=dp[i+1]
        ans+=1
        l=i
if l!=mi and mi!=ma:
    ans+=1
print(ans)




a,b=map(int,input().split())
n=list(map(int,input().split()))
x=0
z=100000
i=0
while i<a:
    if n[i]>x:
        x=n[i]
    i+=1
k=[0]*x
i=0
while i<a:
    k[n[i]-1]+=1
    i+=1
i=x-1
j=1
z=0
c=b
while i>-1:
    if k[i]+z==a:
        break
    if k[i]+z<=c:
        c-=k[i]+z
    else:
        c=b-k[i]-z
        j+=1
    z+=k[i]
    i-=1
if k[x-1]==a:
    print (0)
else:
    print (j)


def main():
    n, k = [int(x) for x in input().split(" ")]
    h = list([int(x) for x in input().split(" ")])
    # f[i] i slice to?
    num = [0 for i in range(max(h)+5)]

    for i in h:
        num[i] += 1

    ans = 0
    now = max(h)
    now_cost = 0
    now_tower = 0
    # print("h", h)
    # print("num", num)
    while now:
        # print(ans, now, now_cost, num[now])
        if num[now] + now_cost <= k:
            pass
        else:
            # print("cut")
            ans += 1
            now_cost = 0
        if num[now] == n:
            break
        now_cost += num[now]
        now -= 1
        num[now] += num[now+1]
    if now_cost != 0:
        # print("cut")
        ans += 1
    print(ans)


def __starting_point():
    main()

__starting_point()

n, k = [int(x) for x in input().split()]
h = [int(x) for x in input().split()]
mih = min(h)
mah = max(h)
if mah == mih:
    print(0)
    return
cotam = dict()
lotam = list()
sotam = set()
for th in h:
    if th > mih:
        if th in sotam:
            cotam[th] += 1
        else:
            sotam.add(th)
            lotam.append(th)
            cotam[th] = 1
lotam.sort(reverse=True)

sc = 0
cc = 0
rk = 0
for i in range(len(lotam)):
    ch = lotam[i]
    nh = (mih if i >= len(lotam) - 1 else lotam[i+1])
    cc += cotam[ch]
    if rk >= cc:
        hrbrk = min(ch-nh, rk // cc)
        rk -= cc * hrbrk
        ch -= hrbrk
    while ch > nh:
        hrbk = min(ch-nh, k // cc)
        sc += 1
        ch -= hrbk
        rk = k - hrbk * cc
print(sc)


3

import math
import sys


DEBUG = False


def inp():
    return sys.stdin.readline().rstrip()


def dprint(*value, sep=' ', end='\n'):
    if DEBUG:
        print(*value, sep=sep, end=end)


def solve(N, K, H):
    H.sort(reverse=True)
    while len(H) >= 2 and H[-2] == H[-1]:
        H.pop()

    width = 0
    cnt = 0
    remain = 0
    for i in range(len(H) - 1):
        h = H[i]
        h1 = H[i + 1]

        width += 1

        height = h - h1

        dprint('i={} h={} h1={} width={} height={} cnt={} remain={}'.format(
            i, h, h1, width, height, cnt, remain))

        if height == 0:
            continue

        if remain + width * height < K:
            remain += width * height
            continue

        dh = (K - remain) // width
        dprint('dh={}'.format(dh))
        assert dh <= height
        remain = 0
        height -= dh
        cnt += 1

        if width * height < K:
            remain += width * height
            continue

        dprint('A: height={} cnt={}'.format(height, cnt))

        t = K // width
        assert t >= 1
        dprint('t={}'.format(t))

        sets = height // t - 1
        dprint('sets={}'.format(sets))
        height -= t * sets
        cnt += sets
        dprint('B: height={} cnt={}'.format(height, cnt))

        while width * height >= K:
            height -= t
            cnt += 1
            dprint('C: height={} cnt={}'.format(height, cnt))

        assert width * height < K
        remain += height * width

    assert remain < K
    if remain > 0:
        cnt += 1

    return cnt


def main():
    N, K = [int(e) for e in inp().split()]
    H = [int(e) for e in inp().split()]
    assert len(H) == N
    print(solve(N, K, H))


def __starting_point():
    main()

__starting_point()

def cell(num):
    if int(num) < num:
        return num + 1
    return num
n, k = list(map(int,input().split()))
hi = list(map(int,input().split()))
hi.sort()
num = 0
if n == 1:
    print(0)
else:
    height = hi[-1]
    sumHeight = 0
    num2 = 1
    for i in range(n-2,-1,-1):
        sumHeight2 = sumHeight + num2 * (height - hi[i])
        if sumHeight2 == k:
            num += 1
            sumHeight = 0
        elif sumHeight2 > k:
            num5 = k // num2
            j = height
            num6 = sumHeight
            while num6 <= k:
                num6 += num2
                j -= 1
            num += 1
            num += (j + 1 - hi[i]) // num5
            sumHeight = (j + 1 - hi[i]) % num5 * num2
        else:
            sumHeight = sumHeight2
        height = hi[i]
        num2 += 1
    if sumHeight > 0:
        num += 1
    print(num)
    
        


n, k = list(map( int, input().split() ))
hs = list( map( int, input().split() ) )
mh = max( hs )
h = []
for i in range( 0, mh + 1 ):
    h.append( 0 )
for hh in hs:
    h[ hh ] += 1

l = 0
good = 0
for i in range( mh, 0, -1 ):
    if h[ i ] == n:
        break
    if l + h[ i ] > k:
        good += 1
        l = h[ i ]
    else:
        l = l + h[ i ]
    h[ i - 1 ] += h[ i ]

print( good + ( 1 if l > 0 else 0 ) )


n, m = map(int, input().split())
b = [0 for i in range(200002)]
c = [0 for i in range(200002)]
hmax = 0
hmin = 200005
a = list(map(int, input().split()))
for i in range(n):
    hmax = max(hmax, a[i])
    hmin = min(hmin, a[i])
    c[a[i]] += 1
b[200000] = c[200000]
for i in range(200000 - 1, -1, -1):
    b[i] = b[i + 1] + c[i]
cur = hmax
ans = 0
#print(b[:5])
while cur > hmin:
    cnt = 0
    while cnt <= m:
        if (cnt + b[cur] <= m) and cur > hmin:
            cnt += b[cur]
            cur -= 1
        else:
            ans += 1
            cnt = 0
            break
        #print(cur, cnt)
    if cur == hmin:
        break
print(ans)

def get_input_list():
	return list(map(int, input().split()))
n,k = get_input_list()
h = get_input_list()
h.sort()
l = []
for i in range(n-1,0,-1):
	if h[i] != h[i-1]:
		for _ in range(h[i] - h[i-1]):
			l.append(n-i)

if len(l) == 0:
	print(0)
else:
	p = 0
	r = 1
	for i in l:
		if p + i <= k:
			p += i
		else:
			r += 1
			p = i
	print(r)

towers, max_bite_size = list(map(int, input().strip().split()))
gen = list(map(int, input().strip().split()))

max_height = 2 * 10 ** 5

heights = [0] * (max_height)
for num in gen:
    heights[num - 1] += 1

num_blocks = 0

num_slices = 0
curr_slice_size = 0

block_sizes = [0] * (max_height)
for idx, num in enumerate(reversed(heights)):
    if num_blocks + num == towers:
        break
    num_blocks += num
    block_sizes[idx] = num_blocks
    if curr_slice_size + num_blocks > max_bite_size:
        num_slices += 1
        curr_slice_size = num_blocks
    else:
        curr_slice_size += num_blocks
if curr_slice_size > 0:
    num_slices += 1
best_so_far = num_slices


num_slices = 0
curr_slice_size = 0

for num in reversed(block_sizes):
    if curr_slice_size + num > max_bite_size:
        num_slices += 1
        curr_slice_size = num
    else:
        curr_slice_size += num
if curr_slice_size > 0:
    num_slices += 1

print(min(num_slices, best_so_far))


from collections import Counter

n, k = list(map(int, input().split()))
h = list(map(int, input().split()))

cnt = Counter(h)

elems = 0
costs = []

hs = list(reversed(sorted(cnt.keys())))
cur_sum = 0
ans = 0

for i in range(len(hs) - 1):
  v, c = hs[i], cnt[hs[i]]
  next_v = hs[i+1]
  diff = v - next_v
  elems += c

  if cur_sum + elems > k:
    ans += 1
    cur_sum = 0
  
  if cur_sum + diff * elems <= k:
    cur_sum += diff * elems
  else:
    if cur_sum != 0:
      diff -= (k - cur_sum) // elems
      ans += 1
    per_cut = k // elems
    cuts = diff // per_cut
    cur_sum = (diff % per_cut) * elems
    ans += cuts
    
ans += cur_sum > 0
print(ans)

n,k=[int(x) for x in input().split()]

d={}
ns=[int(x) for x in input().split()]
minn=min(ns)
ns=[x-minn for x in ns]

for c in ns:
    if c in d:
        d[c]+=1
    else:
        d[c]=1

def eat(i,need):
    al=(ns[i]-ns[i+1])*d[ns[i]]
    if al>need:
        thick=d[ns[i]]
        eath=need//thick
        d[ns[i] - eath]=d[ns[i]]
        ns[i]-=eath
        return i,0
    if al==need:
        d[ns[i+1]]+=d[ns[i]]
        return i+1,0
    if al<need:
        d[ns[i + 1]] += d[ns[i]]
        return i+1,need-al


ns=list(d.keys())
ns.sort(reverse=True)




ans=0

i=0
newn=k

while i<len(ns)-1:
    i,newn=eat(i,newn)
    if newn>0 and i>=len(ns)-1:
        ans+=1
        break
    if newn==0:
        ans+=1
        newn=k





print(ans)






import math as ma
import sys
from decimal import Decimal as dec
from itertools import permutations

def li():
	return list(map(int , input().split()))


# https://www.geeksforgeeks.org/multiplicative-inverse-under-modulo-m/
def modInverse(a , m):
	m0 = m
	y = 0
	x = 1
	if (m == 1):
		return 0
	while (a > 1):
		q = a // m
		t = m
		m = a % m
		a = t
		t = y
		y = x - q * y
		x = t
	if (x < 0):
		x = x + m0
	return x


def num():
	return map(int , input().split())


def nu():
	return int(input())


def find_gcd(x , y):
	while (y):
		x , y = y , x % y
	return x


n,k=num()
h=li()
a=[0]*(max(h)+5)
mx=max(h)
mn=min(h)
fo=True
for i in range(1,n):
	if(h[i]!=h[i-1]):
		fo=False
		break
for i in range(n):
	a[0]+=1
	a[h[i]+1]-=1
for i in range(1,len(a)):
	a[i]=a[i]+a[i-1]
s=a[mx]
cc=0
fl=False
for i in range(mx-1,mn,-1):
	if(s+a[i]>k):
		fl=True
		s=a[i]
		cc+=1
	else:
		fl=False
		s+=a[i]
if(s<=k and fo==False):
	cc+=1
print(cc)

n,k = map(int,input().split())
arr = list(map(int,input().split()))

arr.sort()
heights = []
counter=arr[0]
for i in range(n):
    while arr[i]>=counter:
        heights.append(n-i)
        counter+=1

heights.reverse()


ans=0
container=0
for i in range(len(heights)-1):
    if heights[i]+container<=k:
        container+=heights[i]
    else:
        container=heights[i]
        ans+=1
if container>0:ans+=1

print(ans)

n,k = map(int, input().split())
L = list(map(int, input().split()))
ma = max(L)
f = [0]*(ma+1)
for i in L:
    f[i] += 1
for i in reversed(range(ma)):
    f[i] = f[i] + f[i+1]
c = 0
s = 0
if f[ma] == n:
    print(0)
    quit()
for i in reversed(range(ma+1)):
    if f[i] == n:
        break
    s += f[i]
    if s > k:
        c += 1
        s = f[i]
print(c+1)

n, k = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)

ans = 0
g = A[-1]
h = A[0]
p = 0
i = 1
c = 0
l = 0
while h > g and i < n:
  if A[i] == A[p]:
    p += 1
    i += 1
    continue

  for j in range(A[p] - A[i]):
    c += p+1
    l += 1
    if c > k:
      ans += 1
      h -= l-1
      c = p+1
      l = 0
      if h <= g:
        break
  
  p = i
  i += 1

if h > g:
  ans += 1
  
print(ans)

[n, k] = [int(i) for i in input().split()]

h = [0 for i in range(2 * 10 ** 5 + 1)]

for i in input().split():
	h[int(i)] += 1
h[0] = n
ans = 0
cur = 0
ij = 0
for i in range(2 * 10 ** 5, -1, -1):
	#print(i, ans, cur)
	ij += h[i]
	if ij == n:
		ans += (cur != 0)
		print(ans)
		return
	if cur + ij <= k:
		cur += ij
	else:
		ans += 1
		cur = ij



n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort()
hs1 = [0 for _ in range(a[-1])]
for i in range(n):
    hs1[a[i] - 1] += 1
pluser = 0
hs = [0 for _ in range(a[-1])]
for i in range(a[-1]):
    pluser += hs1[a[-1] - i - 1]
    hs[a[-1] - i - 1] = pluser
floor = a[-1] - 1
ans = 0
count = 0
while floor > a[0] - 1:
    while floor > a[0] - 1 and count + hs[floor] <= k:
        count += hs[floor]
        floor -= 1
    ans += 1
    count = 0
print(ans)



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

h=list(map(int,input().split()))
min1=min(h)

m=max(h)+1 - min1
a=[0 for i in range(m+5)]

for i in range(n):
    h[i]-=min1
    a[h[i]]+=1

for i in range(m-2,-1,-1):
    a[i]+=a[i+1]
cnt=0
cnt1=0
#print(a)
for i in range(m-1,0,-1):
    if(cnt1+a[i]>k):
        cnt1=a[i]
        cnt+=1
    else:
        cnt1+=a[i]
if(cnt1):
    cnt+=1
print(cnt)
    
    
    


    




from collections import defaultdict

def ii():
    return list(map(int, input().split()))

maxv = int(2e5) + 1
n, k = ii()
cnt = defaultdict(int)

for a in ii():
    cnt[a] += 1

for i in range(maxv, -1, -1):
    cnt[i] += cnt[i + 1]

cur, ans = 0, 0
i = maxv

while True:
    if cnt[i] == n:
        if cur:
            ans += 1
        break
    if cur + cnt[i] > k:
        ans += 1
        cur = 0
    cur += cnt[i]
    i -= 1

print(ans)