小田的最大价值

max.in max.out

题目描述

小田有一个长度为 $n$ 的数组和一个数字 $k$。

定义一个数对 $[a_i, a_j](i != j)$ 的价值为：如果 $|a_i-a_j|>k$，则价值为 $max(a_i, a_j)$，否则价值为 $min(a_i, a_j)$。

现在小田想知道，从数组中任选两个数字来组成数对，可能的最大价值是多少。

输入描述

输入包含两行。

第一行两个正整数 $n,k$，表示数组长度和常数 $k$。

第二行 $n$ 个整数 $a_i$，表示数组的元素。

输出描述

输出一个整数，表示最大价值。

输入输出样例

输入 #1

5 3
1 2 3 4 5

输出 #1

5

输入 #2

5 6
1 2 3 4 5

输出 #2

4

说明/提示

【样例 1 解释】

选择数对 $1, 5$，$1-5=4$，满足大于 $k$ 的条件，所以最大价值为 $5$。

【数据范围】

对于 $50 \%$ 的数据，有：$a_i$ 呈升序排列 。

对于所有测试数据，有：$2 \le n \le 10^5，1 \le a_i, k \le 10^9$ 。