please explain the example INPUT and Output of this question

Link to the Question is -:
https://www.codechef.com/AUG18B/problems/KCOMPRES

You are given a sequence of integers A1,A2,…,AN. For an integer K, let's define a K-compressed sequence B1,B2,…,BN as follows:

for each valid i, Bi is a positive integer
for each valid i, if there are exactly X numbers smaller than or equal to Ai in the subsequence Amax(1,i−K),…,Amin(N,i+K), then there must be exactly X numbers smaller than or equal to Bi in the subsequence Bmax(1,i−K),…,Bmin(N,i+K)
B1+B2+⋯+BN is minimum possible
You may notice that for K=N−1 or K=N, this becomes the well-known technique of coordinate compression.

For example, consider the sequence A=[4,2,8,1,4,3,8,1]. If we choose K=1, then the K-compressed sequence will be B=[2,1,2,1,2,1,2,1]. The sum of its elements is 12, which is the minimum.

For a given integer S, find the number of values of K (0≤K≤N) such that the sum of elements of the K-compressed sequence does not exceed S.

Input
The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains two space-separated integers N and S.
The second line contains N space-separated integers A1,A2,…,AN.
Output
For each test case, print a single line containing one integer — the number of values of K such that the sum of the compressed sequence is ≤S.

Constraints
1≤T≤3
1≤N≤105
1≤S≤109
0≤Ai≤109 for each valid i
Subtasks
Subtask #1 (10 points): 1≤N≤100
Subtask #2 (30 points): 1≤N≤1,000
Subtask #3 (60 points): original constraints

Example Input
2
4 8
2 7 1 12
8 20
4 2 8 1 4 3 8 1
Example Output
2
4
Explanation
Example case 1: The possible values of K are 0 and 1.

Registered users can post here. Sign in or register to post.