← 返回题目列表

Codeforces · 837/F

F. 前缀和

中文机器翻译题面 查看原题

考虑函数 p(x),其中 x 是 m 个整数的数组,它返回由 m + 1 个整数组成的数组 y,使得 yi 等于数组 x 的前 i 个元素的总和 (0 ≤ i ≤ m)。

您有一个无限序列的数组 A0、A1、A2...,其中 A0 在输入中给出,并且对于每个 i ≥ 1 Ai = p(Ai - 1)。还有一个正整数 k。您必须找到最小可能的 i,使得 Ai 包含大于或等于 k ​​的数字。

输入

第一行包含两个整数 n 和 k (2 ≤ n ≤ 200000, 1 ≤ k ≤ 1018)。 n 是数组 A0 的大小。

第二行包含 n 个整数 A00、A01...A0n - 1 — A0 的元素 (0 ≤ A0i ≤ 109)。 A0 中至少有两个元素为正。

输出

打印最小值 i,使得 Ai 包含大于或等于 k ​​的数字。

示例

输入 #1

2 2
1 1

输出 #1

1

输入 #2

3 6
1 1 1

输出 #2

2

输入 #3

3 1
1 0 1

输出 #3

0