3773. 坐标压缩

【题目描述】

给定整数序列 $A_1,A_2,...,A_n$。

对于整数 $K(0\le K \le N)$，定义 $K-$压缩序列 $B_1,B_2,\dots,B_n$ 为：

1. 所有 $B_i$ 均为正整数。

2. 对于任意 $i$，如果在子序列 $A_{\max(1,i-k)},...,A_{\min(N,i+k)}$ 中有 $X$ 个元素小于 $A_i$，那么在子序列 $B_{\max(1,i-K)},\ldots,B_{\min(N,i+K)}$ 中必须恰好有 $X$ 个元素小于 $B_i$。

3. $B_1+B_2+...+B_n$ 需要尽量小。

例如，考虑 $A=[4,2,8,1,4,3,8,1]$。如果令 $K$ 等于 $1$，那么 $K-$压缩序列为 $B=[2,1,2,1,2,1,2,1]$，其元素之和为 $12$，达到最小。

对于整数 $S$，求出有多少 $K$ 满足，序列 $K$ 的压缩序列元素之和不超过 $S$。

【输入格式】

输入的第一行包含一个整数 $T$，代表测试数据的组数。接下来是 $T$ 组数据。每组数据的第一行包含两个整数 $N$ 和 $S$。第二行包含 N 个整数 $A_1, A_2,\dots, A_N$。

【输出格式】

输出一行一个整数，满足条件的 K 的数量。

【样例输入】

2
4 8
2 7 1 12
8 20
4 2 8 1 4 3 8 1

【样例输出】

2
4

【数据规模与约定】

对于10%的数据，$1\le N \le 100$ 

对于40%的数据，$1\le N \le 1000$ 

对于100%的数据，$1\le T \le 3$,$1\le S \le 10^9$,$1\le N \le 10^5$,$0\le A_i \le 10^9$

【来源】