Prefix Sums

有一个函数p(x),其中x是一个包含m个整数的数组。p(x)会返回一个长度为m+1的数组y，yi是x数组前i项的和。（0<=i<=m） 例如：x={1,1,1} y=p(x)={0,1,2,3} 现有一列数组A0,A1,A2,……其中A0中的数据会给你，而Ai=p(A(i-1))。有一个整数k，你要求出一个i,在Ai中的某个数大于等于k。 输入第一行是n,k,第二行是A0中的n个数。 要求输出最小的i。

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 $ .

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.

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

2 2
1 1

1

3 6
1 1 1

2

3 1
1 0 1

0