最优旋律

题目描述

Y 同学正在研究一段旋律，该旋律可被抽象为一个长度为 $n$ 的正整数序列 $A = \{a_1, a_2, \ldots, a_n\}$。

为了评估一段旋律的优劣，定义一个序列 $S$ 的和谐度 $H(S)$ 如下：

其中，$|S|$ 表示序列 $S$ 的长度，$\max(S)$ 和 $\min(S)$ 分别表示序列 $S$ 中的最大值和最小值，$k$ 是一个给定的正整数常数。

你需要从原序列 $A$ 中选出一个非空子序列 $S$，使得其和谐度 $H(S)$ 最大。请计算并输出这个最大值。

注：子序列是指从原序列中删除若干个（也可以是 $0$ 个）元素，并保持剩余元素相对顺序不变而形成的序列。

输入格式

本题包含多组测试数据。

第一行包含两个整数 $c$ 和 $T$，分别表示测试点编号和测试数据组数。（对于样例，$c=0$）。

接下来依次输入 $T$ 组测试数据。对于每组测试数据： 第一行包含两个正整数 $n$ 和 $k$，分别表示序列长度和常数。 第二行包含 $n$ 个正整数 $a_1, a_2, \ldots, a_n$，表示旋律序列。

输出格式

对于每组测试数据，输出一行一个整数，表示非空子序列的最大和谐度。

样例

样例输入 #1

0 2
3 3
3 1 8
6 1
1 1 4 5 1 4

样例输出 #1

4
3

数据范围与约定

对于 $100\%$ 的数据，保证：

• $1 \leq T \leq 10$
• $1 \leq n \leq 10^5$
• $1 \leq k, a_i \leq 10^8$

特殊性质说明：

• A：序列 $A$ 是一个公差非负的等差数列。即存在整数 $d \ge 0$，使得 $a_{i+1} - a_i = d$ 对所有 $1 \le i < n$ 成立。
• B：$k = 10^8$。
• C：$k = 1$ 且 $1 \le a_i \le n$。