未排序数组中累加和小于或等于给定值的最长子数组长度

题目描述

给定一个无序数组 $arr$，其中元素可正、可负、可 0。给定一个整数 k，求 $arr$ 所有子数组中累加和小于或等于 k 的最长子数组长度。

例如：$arr = [3, -2, -4, 0, 6], k = -2$。相加和小于等于 $-2$ 的最长子数组为 ${3, -2, -4, 0}$，所以结果返回 $4$。

要求

时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。

输入输出要求

输入描述

第一行两个整数 N, k。N 表示数组长度，k 的定义已在题目描述中给出。

第二行 N 个整数表示数组内的数。

输出描述

输出一个整数表示答案。

示例

输入

5 -2
3 -2 -4 0 6

输出

4

数据范围

• $1 \leqslant N \leqslant 10^5$
• $-10^9 \leqslant k \leqslant 10^9$
• $-100 \leqslant arr_i \leqslant 100$