题目描述

有一个长度为 $n$ 的数组 $a$，其中满足 $i<j$ 的 $(a_i,a_j)$ 称为一个数对。

一个数对的价值定义如下：

• 若 $|a_i-a_j|>k$，则其价值为 $\max(a_i,a_j)$
• 否则价值为 $\min(a_i,a_j)$

其中 $|x|$ 为 $x$ 的绝对值，例如 $|-3|=3,|4|=4$，$\max(x, y)$ 为求解 $x,y$ 的最大值，例如 $\max(3,5)=5$，$\min(x, y)$ 为求解 $x,y$ 的最小值，例如 $\min(3,5)=3$

现在你需要在所有的数对中找到价值最大的那个。

输入格式

第一行输入两个空格隔开的正整数 $n,k$

第二行输入 $n$ 空格隔开的正整数代表 $a_1,a_2,\cdots,a_n$

输出格式

输出一个整数代表最大值

5 3
1 2 3 4 5

5

5 3
1 1 1 1 1

1

5 2
5 1 2 3 4

5

76 945130450306643839
289659096150918798 61009522255100415 442863778056903957 829577396873467219 760018460066984696 84171286480593523 841780468934444642 976821025470863190 646141885334881197 432343618341086242 933930677076554539 901792826604317186 891936015125138920 448880467727950063 614982970793056498 872301783173472750 815024034282111217 548260495550115218 849912929585312366 641922015872534189 254149073325822823 243526897318417748 204922453622736062 649729785116262414 476815250203243283 455852055436213109 518797082950553509 579854541795249762 743298725353570018 195018188970648103 491155766425928326 690300739013840931 415400161851866694 317114952075332434 519553416910476785 369437436763309619 772893429220515708 508190695602496239 998809883427583982 5299713136274604 654619658794854855 840214505991757478 746326407062794510 989034283798432238 133637927767275819 523138790686960811 366284310963020780 970670478149929834 978811383177235105 358977712775060486 15707667245084900 886250607336564988 105649917696606516 881849856591096965 956825222820577133 309544760792566149 312340821983036852 594796297848338500 339767050236204970 905868714567327642 689751053388733987 857994264177064424 178170076384579057 822155022094974485 795673379039390678 524693967655215359 684438428157849410 176090433106083484 39698128640823677 517656523043619752 198965559914358786 281025172602059846 788734710300013086 416818466860280973 196333166525502170 298307404710910376

998809883427583982

5 4
1 2 3 4 5

4

样例 1 解释

一共有 $10$ 组数对，分别是：

• $(a_1,a_2)$，由于 $|a_1-a_2|=1$，由于 $k$ 是 $3$，且 $1<3$，因此它的价值为 $\min(a_1,a_2)=a_1=1$。
• $(a_1,a_3)$，它的价值为 $1$。
• $(a_1,a_4)$，它的价值为 $1$。
• $(a_1,a_5)$，由于 $|a_1-a_5|=4>3$，因此它的价值为 $\max(a_1,a_5)=5$。
• $(a_2,a_3)$，它的价值为 $2$。
• $(a_2,a_4)$，它的价值为 $2$。
• $(a_2,a_5)$，它的价值为 $2$。
• $(a_3,a_4)$，它的价值为 $3$。
• $(a_3,a_5)$，它的价值为 $3$。
• $(a_4,a_5)$，它的价值为 $4$。

选择数对 $(a_1,a_5)$ 可以构成最大价值。

提示

对于 $50\%$ 的数据满足 $2\leq n,k\leq 10^3,1\leq a_i\leq 10^3$

对于 $80\%$ 的数据满足 $2\leq n\leq 10^5,1\leq a_i,k\leq 10^9$

对于 $100\%$ 的数据满足 $2\leq n\leq 10^5,1\leq a_i,k\leq 10^{18}$