Consider the function p(x), where x is an array of m integers, which returns an array y consisting of m + 1 integers such that y_{i} is equal to the sum of first i elements of array x (0 ≤ i ≤ m).

You have an infinite sequence of arrays A^0, A^1, A^2..., where A^0 is given in the input, and for each i ≥ 1 A^{i} = p(A^{i} - 1). Also you have a positive integer k. You have to find minimum possible i such that A^{i} contains a number which is larger or equal than k.


-----Input-----

The first line contains two integers n and k (2 ≤ n ≤ 200000, 1 ≤ k ≤ 10^18). n is the size of array A^0.

The second line contains n integers A^0_0, A^0_1... A^0_{n} - 1 — the elements of A^0 (0 ≤ A^0_{i} ≤ 10^9). At least two elements of A^0 are positive.


-----Output-----

Print the minimum i such that A^{i} contains a number which is larger or equal than k.


-----Examples-----
Input
2 2
1 1

Output
1

Input
3 6
1 1 1

Output
2

Input
3 1
1 0 1

Output
0

Difficulty: interview

Starter code:

Solutions:
n,k = list(map(int,input().split()));
a = list(map(int,input().split()));

if max(a) >= k:
    print(0)
    return

lx = 0
while a[lx] == 0:
    lx+=1

lo,hi = 1,k

def can(x):
    bc = 1
    tot = 0
    for i in range(n-lx):
        if(bc >= k):
            return True
        tot += bc*a[n-1-i]
        bc *= (x+i)
        bc = bc//(i+1)
        if(tot >= k):
            return True
    return tot >= k

while lo < hi :
    mid = (lo+hi)//2
    cancan = can(mid)
    #print(mid,cancan)
    if cancan : hi = mid
    else : lo = mid + 1

print(lo)


from itertools import *
n, k = list(map(int, input().split()))
*A, = list(map(int, input().split()))
alc = 0
for v in A:
    if v > 0:
        alc += 1
if max(A) >= k:
    print(0)
elif alc <= 20:
    l = 0
    r = int(1e18)
    while l + 1 < r:
        m = (l + r) // 2
        s = 0
        for i in range(n):
          if A[i] > 0:
            s2 = 1
            for j in range(n - i - 1):
                s2 *= m + j
                s2 //= j + 1
                if s2 >= k:
                    break
            s += s2 * A[i]
            if s >= k:
                break
        if s >= k:
            r = m
        else:
            l = m
    print(r)
else:
    ans = 0
    while True:
        ans += 1
        for i in range(1, n):
            A[i] += A[i - 1]
        if A[-1] >= k:
            break
    print(ans)
           


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

v = []
for x in l:
    if x != 0 or v:
        v.append(x)

def bruteforce(v, k):
    ret = 0
    while True:
        accm = 0
        for i in range(len(v)):
            if v[i] >= k: return ret
            accm += v[i]
            v[i] = accm
        ret += 1
    return ret

def smarty(v, k):
    def triang(x):
        return x*(x+1)//2
    l, r = 0, 10**18
    ans = 10**18
    while l<=r:
        h = (l+r)//2
        f0 = v[0]
        f1 = h*v[0] + v[1]
        f2 = triang(h)*v[0] + h*v[1] + v[0] if n == 3 else 0
        if max(f0, f1, f2) >= k:
            r = h-1
            ans = min(ans, h)
        else:
            l = h+1
    return ans

n = len(v)
if n>3:
    print(bruteforce(v, k))
else:
    print(smarty(v, k))


'''

0  |  a1       a2         a3
1  |  a1       a1+a2      a1+ a2+a3
2  |  a1      2a1+a2     3a1+2a2+a3
...      ...        ...
cada celda depende de la izq y la superior, es como numeros
combinatorios, el a1 es triang(k) en 3, y los inmediatamente anteriores
por k (con k=0 es perm original!)
'''
n, k = list(map(int, input().split(" ")))
l = list(map(int, input().split(" ")))

v = []
for x in l:
    if x != 0 or v:
        v.append(x)

def bruteforce(v, k):
    ret = 0
    while True:
        accm = 0
        for i in range(len(v)):
            if v[i] >= k: return ret
            accm += v[i]
            v[i] = accm
        ret += 1
    return ret

def smarty(v, k):
    def triang(x):
        return x*(x+1)//2
    l, r = 0, 10**18
    ans = 10**18
    while l<=r:
        h = (l+r)//2
        f0 = v[0]
        f1 = h*v[0] + v[1]
        f2 = triang(h)*v[0] + h*v[1] + v[0] if n == 3 else 0
        if max(f0, f1, f2) >= k:
            r = h-1
            ans = min(ans, h)
        else:
            l = h+1
    return ans

n = len(v)
if n>3:
    print(bruteforce(v, k))
else:
    print(smarty(v, k))


s=input().split()
n=int(s[0])
k=int(s[1])
L=list(map(int,input().split()))

lx=0
while L[lx]==0:
    lx+=1
A=[]
for i in range(lx,n):
    A.append(L[i])
n=len(A)
n=len(A)
def good(l):
    coeff=1
    tot=0
    for i in reversed(list(range(n))):
        tot+=coeff*A[i]
        if tot>=k:
            return True
        coeff=(coeff*(n-i-1+l))//(n-i)
    return False
ans=0
for i in range(1,10):
    if good(i):
        ans=i
        break
if ans==0:
    l=1
    r=k
    while True:
        if l==r:
            ans=l
            break
        if l+1==r:
            if good(l):
                ans=l
            else:
                ans=r
            break
        m=(l+r)//2
        if good(m):
            r=m
        else:
            l=m+1
for i in range(n):
    if A[i]>=k:
        ans=0
print(ans)


def p(arr):
	for i in range(1,len(arr)):
		arr[i]+=arr[i-1]
	return arr

def max_element(arr):
	x=0
	for i in arr:
		x=max(x,i)
	return x

def kek(a,b):
	if (a<=b):
		return 1
	else:
		return 0

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

def matmul(m1,m2):
	s=0     #сумма
	t=[]    #временная матрица
	m3=[] # конечная матрица
	if len(m2)!=len(m1[0]):
		print("333")       
	else:
		r1=len(m1) #количество строк в первой матрице
		c1=len(m1[0]) #Количество столбцов в 1   
		r2=c1           #и строк во 2ой матрице
		c2=len(m2[0])  # количество столбцов во 2ой матрице
		for z in range(0,r1):
			for j in range(0,c2):
				for i in range(0,c1):
					s=s+m1[z][i]*m2[i][j]
					s=min(s,k)
				t.append(s)
				s=0
			m3.append(t)
			t=[]           
	return m3	

def exp(m,p):
	if (p==1):
		return m
	if (p%2==0):
		w=exp(m,p//2)
		return matmul(w,w)
	else:
		return matmul(m,exp(m,p-1))



a=[int(x) for x in input().split()]
ind=0
while a[ind]==0:
	ind+=1
a=a[ind:]
n=len(a)
if (max_element(a)>=k):
	print(0)
else:
	a=[a]
	if (n>=10):
		res=0
		while(max_element(a[0])<k):
			res+=1
			a[0]=p(a[0])
		print(res)
	elif n==2:
		x1=a[0][0]
		x2=a[0][1]
		print((k-x2+x1-1)//x1)
	else:
		m=[]
		for i in range(n):
			m+=[[kek(i,j) for j in range(n)]]
		l=0;
		r=10**18
		while(l+1<r):
			mid=(l+r)//2;
			b=matmul(a,exp(m,mid))
			if max_element(b[0])<k:
				l=mid
			else:
				r=mid
		print(r)
		
	


from sys import stdin, stdout
from math import factorial
from math import log10


def check(pw, values, k):
    n = len(values)
    
    matr = [[0 for i in range(n)] for j in range(n)]
    res = [[0 for i in range(n)] for j in range(n)]
    pp = [[0 for i in range(n)] for j in range(n)]
    
    for i in range(n):
        for j in range(n):
            matr[i][j] = int(i >= j)
    
    for i in range(n):
        res[i][i] = 1
        
    while pw:
        if pw & 1:
            for i in range(n):
                for j in range(n):
                    pp[i][j] = 0
            
            for i in range(n):
                for j in range(n):
                    for z in range(n):
                        pp[i][j] += res[i][z] * matr[z][j]
            
            for i in range(n):
                for j in range(n):
                    res[i][j] = pp[i][j]
        
        for i in range(n):
            for j in range(n):
                pp[i][j] = 0        

        for i in range(n):
            for j in range(n):
                for z in range(n):
                    pp[i][j] += matr[i][z] * matr[z][j]        

        
        for i in range(n):
            for j in range(n):
                matr[i][j] = pp[i][j]

        pw >>= 1
    
    ans = 0
    for i in range(n):
        ans += values[i] * res[i][0]
            
    
    return ans >= k


def stupid(values, n, k):
    ans = values[:]
    
    if max(ans) >= k:
        return 0
    
    cnt = 0
    while ans[-1] < k:
        for i in range(1, n):
            ans[i] += ans[i - 1]
        
        cnt += 1
        q = ans[-1]
    
    return cnt


def clever(values, n, k):
    if max(values) >= k:
        return 0
    
    l, r = 0, 10 ** 18 + 100
    
    while r - l > 1:
        m = (l + r) >> 1
        
        if check(m, values, k):
            r = m
        else:
            l = m
            
    return r


def main():
    n, k = map(int, stdin.readline().split())
    values = list(map(int, stdin.readline().split()))[::-1]
    
    while not values[-1]: #Проблема в том что ты удаляешь
        values.pop()
    
    n = len(values)

    
    if n >= 10:
        stdout.write(str(stupid(values[::-1], n, k)) + '\n')
    else:
        stdout.write(str(clever(values, n, k)) +  '\n')
    
    
main()

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

ptr = 0
while a[ptr]==0:
  ptr += 1

def check(x):
  
  if x==0:
    return max(a) >= k
    
  binomial = 1
  sum = 0
  
  for i in range(n-ptr):
    if binomial >= k:
      return True
    sum += binomial * a[n-i-1]
    binomial *= (x+i)
    binomial //= (i+1)
    if sum >= k:
      return True
  return False

lo,hi = 0, k

while lo < hi:

  md = (lo+hi) // 2
  
  if check(md):
    hi = md;
  else:
    lo = md + 1
    
print(lo)


s = input().split()
n = int(s[0]); k = int(s[1])
s = input().split()
a = [1]
for i in range(1, n + 1):
	a.append(int(s[i - 1]))

for i in range(1, n + 1):
	if (a[i] >= k):
		print((0)); return

def C(nn, kk):
	nonlocal k
	prod = 1
	kk = min(kk, nn - kk)
	# print(nn, nn - kk + 1)
	for i in range(1, kk + 1):
		# print("///" + str(i))
		prod *= nn - i + 1
		prod = prod // i
		if (prod >= k):
			return -1
	if (prod >= k):
		return -1
	return prod

def holyshit(pwr):
	nonlocal n, k, a
	sum = 0
	for i in range(n, 0, -1):
		if (a[i] == 0):
			continue
		prod = C(pwr - 1 + n - i, pwr - 1)
		if (prod == -1): 
			return True
		sum += prod * a[i]
		if (sum >= k):
			return True
	# print("wait, the sum is..." + str(sum))
	return False

left = 1; right = int(1e19); ans = int(1e19)
while left <= right:
	mid = (left + right) >> 1
	# print("/" + str(left) + " " + str(mid) + " " + str(right))
	if (holyshit(mid)):
		# print("////okay")
		ans = mid
		right = mid - 1
	else:
		# print("////notokay")
		left = mid + 1
print(ans)
# print(int(1e19))
# k = int(1e18)
# # print(C(6, 3))
# # print(C(10, 1))
# # print(C(7, 5))
# # print(C(8, 2))


from math import factorial
def ncr(n, r):
    ans = 1
    for i in range(r):
        ans*=n-i
    for i in range(r):
        ans//=i+1
    return ans

n,k = list(map(int, input().split()))
inp = list(map(int,input().split()))
nz = 0
seq = []
for i in range(n):
    if(inp[i]!=0):
        nz = 1
    if(nz!=0):
        seq.append(inp[i])

if(max(seq) >= k):
    print("0")
    return

if(len(seq) <= 8):
    seq.reverse()
    mn = 1
    mx = pow(10,18)
    while(mn < mx):
        mid = (mn + mx)//2
        curr = 0
        for i in range(len(seq)):
            curr+=seq[i]*ncr(mid+i-1, i)
        if(curr>=k):
            mx = mid
        else:
            mn = mid + 1
    print(mn)
    return
for i in range(1000):
    for j in range(1,len(seq)):
        seq[j]+=seq[j-1]
    if(max(seq) >= k):
        print(i+1)
        return