You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

$x$ 是一个长度为 $n$ 的数组，下标编号从 $0$ 开始。

定义一个函数 $y=p(x)$， 返回一个长度为 $n$ 的数组，其中 $y$ 满足 $y_i=\sum_{j=0}^{i}x_j$，$0\leq i\leq n-1$。

给出一个数组 $x$ ，令 $A_0=x$，$A_{i+1} = p(A_i)$ 。由此递推式能计算出无穷个数组$A_0,A_1,A_2,A_3,...$

再给一个正整数 $k$ ，求满足 $A_i$ 中包含一个大于等于 $k$ 的元素这个条件的最小的 $i$ 。

输入格式

第一行两个整数 $n$ 和 $k$ 。

第二行 $n$ 个整数，$x_0, x_1, x_2, …, x_{n-1}$，保证其中最少两个数为正数。

输出格式

输出最小的满足$A_i$ 中包含一个大于等于 $k$ 的元素这个条件的 $i$。

输入样例1

2 2
1 1

输出样例1

1

输入样例2

3 6
1 1 1

输出样例2

2

输入样例3

3 1
1 0 1

输出样例3

0

数据范围

$30\%$，$n \leq 1000，k \leq 100000$

$50\%$，$k\leq 10^9$

$100 \%$，$n \leq 200000, k \leq 10^{18}, 0\leq x_i \leq 10^9$