Link to the Question is -:
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.
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.
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.
0≤Ai≤109 for each valid i
Subtask #1 (10 points): 1≤N≤100
Subtask #2 (30 points): 1≤N≤1,000
Subtask #3 (60 points): original constraints
2 7 1 12
4 2 8 1 4 3 8 1
Example case 1: The possible values of K are 0 and 1.