한 번에 옮길 우편 행낭

문제

우체국의 분류대에는 우편 행낭 N개가 왼쪽부터 한 줄로 놓여 있다. 행낭에는 왼쪽부터 1번부터 N번까지 번호가 붙어 있고, 각 행낭에는 한 개 이상의 우편물이 들어 있다. 담당자는 운반 카트에 실을 행낭을 고르려 한다. 분류대의 다른 행낭을 옮기지 않고 작업하기 위해, 고른 행낭은 반드시 번호가 연속된 하나의 구간을 이루어야 한다. 카트로 보내는 우편물은 모두 같은 작업 구역에서 처리된다. 해당 구역의 작업을 시작하려면 이번에 보내는 우편물이 K개 이상이어야 한다. 따라서 담당자는 고른 구간에 들어 있는 우편물 수의 합이 K 이상이 되도록 해야 한다. 행낭을 열거나 일부 우편물만 꺼내는 일은 허용되지 않으며, 선택한 행낭에 든 우편물은 전부 함께 보낸다. 우편물 수가 K를 넘는 것은 허용된다. 행낭을 하나 실을 때마다 별도의 확인 절차가 필요하므로, 담당자는 조건을 만족하는 구간 중 행낭 수가 가장 적은 구간을 원한다. 우편물 수가 가장 적거나 K에 가장 가까운 구간을 찾는 것이 아니라, 선택한 행낭의 개수를 최소화해야 한다. 이 문제에서는 카트의 무게나 부피 제한은 따로 고려하지 않는다. 각 행낭의 우편물 수가 주어질 때, 우편물을 K개 이상 보내기 위해 선택해야 하는 최소 행낭 수를 구한다. 같은 최소 개수를 만드는 구간이 여러 개라면 어느 구간을 택해도 결과는 같으므로 그 개수만 출력한다. 빈 구간은 선택할 수 없다. 모든 행낭을 함께 골라도 우편물이 K개에 미치지 못한다면 조건을 만족하는 구간이 없는 것으로 처리한다.

입력

첫째 줄에 정수 N과 K가 공백으로 주어진다. 1 ≤ N ≤ 200,000, 1 ≤ K ≤ 1,000,000,000이다.
둘째 줄에 각 행낭의 우편물 수를 나타내는 정수 A_1, A_2, ..., A_N이 공백으로 주어진다. 모든 i에 대해 1 ≤ A_i ≤ 1,000이다.

출력

조건을 만족하는 연속 구간의 최소 행낭 수를 정수 하나로 출력한다. 조건을 만족하는 구간이 없으면 0을 출력한다.

7 14
4 2 6 1 5 3 2

4

4 20
3 4 2 5

0

5 8
2 8 1 4 3

1

출처: Devin.KR 자체 제작