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 yi is equal to the sum of first i elements of array x (0 \le i \le m).

You have an infinite sequence of arrays A0,A1,A2..., where A0 is given in the input, and for each i \ge 1 Ai=p(Ai-1). Also you have a positive integer k. You have to find minimum possible i such that Ai contains a number which is larger or equal than k.

The first line contains two integers n and k (2 \le n \le 200000, 1 \le k \le 1018). n is the size of array A0.

The second line contains n integers A00,A01... A0n-1 - the elements of A0 (0 \le A0i \le 109). At least two elements of A0 are positive.

Print the minimum i such that Ai contains a number which is larger or equal than k.