Maximum Subarray Starting Index Near Threshold

Given an array of n positive integers representing execution times and a threshold value t, find the starting index of the maximum-length contiguous subarray such that the sum of the subarray is as close as possible to t without exceeding it. In case of multiple subarrays of the same maximum length, choose the one with the larger sum. Note that if no subarray can meet the condition (i.e., every element exceeds t), return 0.

The problem can be formalized as follows:

Given integers \(n\) and \(t\) and an array \(A\) of length \(n\), find the smallest index \(i\) such that there exists a contiguous subarray \(A[i\ldots j]\) for which:

[ \begin{aligned} &\text{Length } \ell = j-i+1 \text{ is maximized}, \ &\text{subject to } \sum_{k=i}^{j} A[k] \leq t, \ &\text{and if there is a tie in } \ell, \text{ choose the one with the maximum } \sum_{k=i}^{j} A[k]. \end{aligned} ]

Your task is to implement a solution that reads from stdin and outputs the answer to stdout.

inputFormat

The first line contains two integers, n (the number of execution times) and t (the threshold).

The second line contains n positive integers separated by spaces representing the execution times.

outputFormat

Output a single integer representing the starting index (0-based) of the maximum-length contiguous subarray whose sum is closest to t without exceeding it.

5 15
1 2 3 4 5

0