#P0886. 最短达标子段

最短达标子段

题目描述

给定一个长度为 nn 的整数序列 a1,a2,…,ana_1,a_2,\dots,a_n(1≤n≤2×1051\le n\le 2\times 10^5,−109≤ai≤109-10^9\le a_i\le 10^9)和一个整数 XX(−1014≤X≤1014-10^{14}\le X\le 10^{14},XX 也可以为负数或 00)。序列中的元素可以为负数,也可以为 00。

称 al,al+1,…,ara_l,a_{l+1},\dots,a_r 是该序列的一个连续子段(其中 1≤l≤r≤n1\le l\le r\le n),它的长度为 r−l+1r-l+1,它的元素之和为 ∑i=lrai\sum_{i=l}^{r}a_i。子段必须非空,也就是说长度至少为 11。

请你找出长度最小的连续子段,使得该子段的元素之和大于等于 XX,并输出这个最小长度。如果不存在这样的连续子段,请输出 -1。

输入格式

输入共两行。

第一行包含两个整数 nn 和 XX(1≤n≤2×1051\le n\le 2\times 10^5,−1014≤X≤1014-10^{14}\le X\le 10^{14},XX 也可以为负数或 00),分别表示序列的长度与目标值,两个整数之间用一个空格分隔。

第二行包含 nn 个整数 a1,a2,…,ana_1,a_2,\dots,a_n(−109≤ai≤109-10^9\le a_i\le 10^9),表示给定的序列,相邻两个整数之间用一个空格分隔。这里的每个元素都可以是负数、00 或正数。

输出格式

输出一行一个整数,表示元素之和大于等于 XX 的非空连续子段的最小长度。

如果不存在这样的子段,输出 -1。

样例

5 10
-20 6 -2 4 4
4
3 10
5 4 -1
-1
2 -2
-3 -3
-1