考虑函数 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