Educational Codeforces Round 26 |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

binary search

brute force

combinatorics

math

matrices

*2400

No tag edit access

The problem statement has recently been changed. View the changes.

×
F. Prefix Sums

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputConsider 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

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/19/2024 06:05:09 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|