Problem5666--Segment with Big Sum

5666: Segment with Big Sum

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

Description

Given an array of $n$ integers $a_i$. Let's say that the segment of this array $a[l,\ r]\ (1≤l≤r≤n)$ is good if the sum of elements on this segment is at least $s$. 
Your task is to find the shortest good segment.
给定$n$个整数$a_i$,求子段和大于等于$s$的最短子段

Input

The first line contains integers $n,\ s\ (1≤n≤10^5, 1≤s≤10^{18})$. 
The second line contains integers $a_i\ (1≤a_i≤10^9)$.
第一行 输入整数 $n, s$
第二行 输入整数序列$a_i$

Output

Print one integer, the length of the shortest good segment. If there are no such segments, print $-1$.
输出子段和大于等于$s$的最短子段的长度。如果不存在这样的子段,输出-1。

Sample 1 Input

7 20
2 6 4 3 6 8 9

Sample 1 Output

3

HINT

相同题目:CodeForces

Source/Category

基础算法 4.5.双指针