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

Source: codeforces | Difficulty: VERY_HARD
Tags: Sorting

Combinatorics

Complete search

Mathematics

Matrices


Solutions:
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()


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


(n, k) = map(int, input().split(' '))
l = 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))


(n, k) = 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])
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)


import sys

def mul(a, b):
	n = len(a)
	m = [[0 for j in range(n)] for i in range(n)]
	for i in range(n):
		for j in range(n):
			for k in range(n):
				m[i][j] += a[i][k] * b[k][j]
	return m
(n, k) = [int(i) for i in input().split(' ')]
a = [int(i) for i in input().split(' ')]
if max(a) >= k:
	print(0)
	sys.exit(0)
a0 = []
s = 0
for i in range(n):
	s += a[i]
	if s > 0:
		a0.append(a[i])
n = len(a0)
if n > 30:
	it = 0
	while True:
		it += 1
		for j in range(1, n):
			a0[j] += a0[j - 1]
			if a0[j] >= k:
				print(it)
				sys.exit(0)
else:
	m = [[[int(i >= j) for j in range(n)] for i in range(n)]]
	for l in range(0, 62):
		m.append(mul(m[-1], m[-1]))
	ans = 0
	u = [[int(i == j) for j in range(n)] for i in range(n)]
	for l in range(62, -1, -1):
		u2 = mul(u, m[l])
		val = 0
		for i in range(0, n):
			val += a0[i] * u2[-1][i]
		if val < k:
			u = u2
			ans += 2 ** l
	print(ans + 1)


import sys
from time import sleep

def increment(a):
	for i in range(1, n):
		a[i] += a[i - 1]

class DimensionError(ValueError):
	pass

class Matrix:

	def __init__(self, m, n, data=None):
		self.m = m
		self.n = n
		self.mn = m * n
		if data is None:
			self.data = [0] * self.mn
		elif len(data) == self.mn:
			self.data = data
		else:
			raise DimensionError()

	def __repr__(self):
		return 'Matrix({}, {}, {})'.format(self.m, self.n, self.data)

	def __call__(self, i, j):
		if i < 0 or i >= self.m or j < 0 or (j >= self.n):
			raise IndexError('({}, {})'.format(i, j))
		return self.data[i * self.n + j]

	def set_elem(self, i, j, x):
		if i < 0 or i >= self.m or j < 0 or (j >= self.n):
			raise IndexError('({}, {})'.format(i, j))
		self.data[i * self.n + j] = x

	def add_to_elem(self, i, j, x):
		if i < 0 or i >= self.m or j < 0 or (j >= self.n):
			raise IndexError('({}, {})'.format(i, j))
		self.data[i * self.n + j] += x

	def last(self):
		return self.data[-1]

	def scalar_mul_ip(self, s):
		for i in range(len(data)):
			self.data[i] *= s
		return self

	def scalar_mul(self, s):
		data2 = [x * s for x in self.data]
		return Matrix(self.m, self.n, data2)

	def matrix_mul(self, B):
		if self.n != B.m:
			raise DimensionError()
		m = self.m
		p = self.n
		n = B.n
		C = Matrix(m, n)
		for i in range(m):
			for j in range(n):
				for k in range(p):
					C.add_to_elem(i, j, self(i, k) * B(k, j))
		return C

	def __imul__(self, x):
		if isinstance(x, int):
			return self.scalar_mul_ip(x)
		else:
			return NotImplemented

	def __mul__(self, x):
		if isinstance(x, int):
			return self.scalar_mul(x)
		elif isinstance(x, Matrix):
			return self.matrix_mul(x)
		else:
			return NotImplemented

	def __rmul__(self, x):
		if isinstance(x, int):
			return self.scalar_mul(x)
		else:
			return NotImplemented
(n, k) = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
assert len(a) == n
for (i, x) in enumerate(a):
	if x > 0:
		break
if i > 0:
	a = a[i:]
n = len(a)
if max(a) >= k:
	print(0)
	sys.exit(0)
else:
	increment(a)
if n > 10:
	p = 0
	while a[-1] < k:
		increment(a)
		p += 1
	print(p + 1)
	sys.exit(0)
if a[-1] >= k:
	print(1)
	sys.exit(0)
A = Matrix(n, n)
for i in range(n):
	for j in range(i + 1):
		A.set_elem(i, j, 1)
X = Matrix(n, 1, a)
pA = [A]
i = 0
while (pA[i] * X).last() < k:
	pA.append(pA[i] * pA[i])
	i += 1
B = Matrix(n, n)
for i in range(n):
	B.set_elem(i, i, 1)
p = 0
for (i, A2) in reversed(list(enumerate(pA))):
	B2 = B * A2
	if (B2 * X).last() < k:
		p += 1 << i
		B = B2
X = B * X
p += 1
increment(X.data)
print(p + 1)


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)
		exit(0)

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

def holyshit(pwr):
	global 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
	return False
left = 1
right = int(1e+19)
ans = int(1e+19)
while left <= right:
	mid = left + right >> 1
	if holyshit(mid):
		ans = mid
		right = mid - 1
	else:
		left = mid + 1
print(ans)


(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)
	if cancan:
		hi = mid
	else:
		lo = mid + 1
print(lo)


from itertools import *
(n, k) = map(int, input().split())
(*A,) = 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(1e+18)
	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) = map(int, input().split())
A = []
for x in map(int, input().split()):
	if x > 0 or len(A) > 0:
		A.append(x)
if max(A) >= k:
	print(0)
elif len(A) == 2:
	if (k - A[1]) % A[0] == 0:
		print((k - A[1]) // A[0])
	else:
		print((k - A[1]) // A[0] + 1)
elif len(A) == 3:
	left = 0
	right = 10 ** 18
	while left < right:
		mid = (left + right) // 2
		if A[2] + A[1] * mid + A[0] * mid * (mid + 1) // 2 >= k:
			right = mid
		else:
			left = mid + 1
	print(left)
else:
	ans = 0
	while A[-1] < k:
		ans += 1
		for i in range(1, len(A)):
			A[i] += A[i - 1]
	print(ans)


mod = 10 ** 9 + 7
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
a.reverse()

def sol():
	l = 0
	r = 10 ** 18
	mid = 0
	p = 1
	sum = 0
	while r - l > 1:
		mid = (l + r) // 2
		p = 1
		sum = 0
		for i in range(n):
			if a[i] * p >= k:
				r = mid
				break
			sum += a[i] * p
			if sum >= k:
				r = mid
				break
			if i + 1 < n:
				p = p * (mid + i) // (i + 1)
			if p >= k:
				r = mid
				break
		if r != mid:
			l = mid + 1
	p = 1
	sum = 0
	for i in range(n):
		if a[i] * p >= k:
			return l
		sum += a[i] * p
		if sum >= k:
			return l
		if i + 1 < n:
			p = p * (l + i) // (i + 1)
		if p >= k:
			return l
	return r
for i in range(n - 1, -1, -1):
	if a[i] != 0:
		break
	else:
		n -= 1
if max(a) >= k:
	print(0)
else:
	print(sol())


import sys
(n, k) = map(int, input().split())
ar = []
br = map(int, input().split())
for x in br:
	if x > 0 or len(ar) > 0:
		ar.append(x)
if max(ar) >= k:
	print(0)
elif len(ar) == 2:
	print((k - ar[1] + ar[0] - 1) // ar[0])
elif len(ar) == 3:
	(ini, fin) = (0, 10 ** 18)
	while ini < fin:
		mid = (ini + fin) // 2
		if ar[2] + ar[1] * mid + ar[0] * mid * (mid + 1) // 2 >= k:
			fin = mid
		else:
			ini = mid + 1
	print(ini)
else:
	ans = 0
	while ar[-1] < k:
		ans += 1
		for i in range(1, len(ar)):
			ar[i] += ar[i - 1]
	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])
		r2 = c1
		c2 = len(m2[0])
		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)


inf = 100000000000000000000

def choose(n, r):
	r = min(r, n - r)
	if r >= 35:
		return inf
	(num, denum) = (1, 1)
	for i in range(0, r):
		num *= n - i
	for i in range(0, r):
		denum *= i + 1
	return num // denum
(n, k) = map(int, input().split())
P = list(map(int, input().strip().split()))[:n]
flag = 0
for x in P:
	if x >= k:
		flag = 1
		print(0)
		break
if flag == 0:
	(lo, hi, ans) = (1, 1000000000000000000, 1000000000000000000)
	while lo <= hi:
		mid = (lo + hi) // 2
		sum = 0
		for i in range(1, n + 1):
			if P[i - 1] > 0:
				sum += P[i - 1] * choose(mid + n - i - 1, n - i)
			if sum >= k:
				break
		if sum >= k:
			hi = mid - 1
			ans = mid
		else:
			lo = mid + 1
	print(ans)