1527: CF837 - F. Prefix Sums
[Creator : ]
Description
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,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$.
Sample 1 Input
2 2
1 1
Sample 1 Output
1
Sample 2 Input
3 6
1 1 1
Sample 2 Output
2
Sample 3 Input
3 1
1 0 1
Sample 3 Output
0