RoAlgo Contest #5 - Back to School Edition | fulger

Task

You are given an array with $n$ natural numbers, which is sorted in increasing order. The task is to find the subarray with a sum of at least $k$ that has the minimum difference between the maximum and minimum values in the subarray. If there are multiple such subarrays, find the one with the minimum length.

Input data

The first line contains two integers, $n$ and $k$, representing the number of numbers in the array, and the sum we want to achieve.

The next line contains $n$ numbers sorted in increasing order, representing the values in the array.

Output data

The first line will contain two numbers, representing the minimum difference required and the minimum length of a subarray that meets the given property.

Constraints and clarifications

• $1 \leq n \leq 200 \ 000$
• $1 \leq k \leq 10^9$
• $1 \leq v_1 \leq v_2 \leq \dots \leq v_n \leq 1 \ 000 \ 000$
• A subarray represents values in the array of some consecutive indices.
• It is guaranteed that there is at least one subarray with a sum of at least $k$.

Example 1

stdin

7 10
2 3 3 4 4 5 7

stdout

1 3

Explanation

The minimum difference is obtained if we take the subarray $(3, 3, 4)$, the sum being $10$, the difference between the maximum and minimum values being $1$, and the minimum length being $3$.

Example 2

stdin

15 85
1 5 6 7 7 7 8 8 9 9 11 13 15 16 17

stdout

7 10

Explanation

$6 + 7 + 7 + 7 + 8 + 8 + 9 + 9 + 11 + 13 = 85$