Prefix Sums

1000ms

262144K

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⁰, A¹, A²..., where A⁰ is given in the input, and for each i ≥ 1 Aⁱ = p(A^i - 1). Also you have a positive integer k. You have to find minimum possible i such that Aⁱ 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¹⁸). n is the size of array A⁰.

The second line contains n integers A⁰₀, A⁰₁... A⁰_n - 1 — the elements of A⁰ (0 ≤ A⁰_i ≤ 10⁹). At least two elements of A⁰ are positive.

Output:

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

Sample Input:

2 2
1 1

Sample Output:

Sample Input:

3 6
1 1 1

Sample Output:

Sample Input:

3 1
1 0 1

Sample Output:

Informação

Provedor Codeforces

Código CF837F