鱼鱼跃龙门

鱼鱼一直有一个跃龙门的梦想。

现在有 $n$ 座龙门从左到右排成一排，第 $i$ 座龙门的高度为 $a_i$。

鱼鱼需要依次跳过这些龙门。

第一次跳跃时，鱼鱼可以选择一个 初始跳跃高度 $x$。

当鱼鱼成功跳过一座龙门后，鱼鱼的跳跃高度会发生变化：

• 如果当前跳跃高度 恰好等于 该龙门高度 $a_i$，则下一次跳跃高度 减少 $k$；

• 如果当前跳跃高度 大于 该龙门高度 $a_i$，则下一次跳跃高度 减少 $1$；

如果在某一次跳跃时，当前跳跃能力 小于 当前龙门的高度，则无法跳过该龙门。

鱼鱼想找到一个最小的初始跳跃高度 $x$，使得她能够成功跳过所有 $n$ 座龙门。但鱼鱼只是一条鱼，并不会计算这么复杂的问题，所以请你帮助她完成这个计算。

输入描述

第一行输入两个正整数 $n(1 \le n \le 2 × 10^5)，k(1 \le k \le 2 × 10^5)$ 分别表示有 $n$ 座龙门以及会减少的高度值 $k$ 。

第二行包含 $n$ 个正整数 $a_1, a_2, a_3, \dots , a_n (1 \le a_i \le 2 × 10^5)$ 表示每座龙门的高度。

输出描述

输出一个整数，表示能跳过所有龙门的最小初始跳跃高度 $x$ 。

示例1

输入

5 3
3 3 3 3 3

输出

7

说明

当 x = 7 时：

龙门    当前跳跃高度    龙门高度    跳跃后高度
1    7    3    7 > 3 → 6
2    6    3    6 > 3 → 5
3    5    3    5 > 3 → 4
4    4    3    4 > 3 → 3
5    3    3    3 = 3 → 0

所有龙门均可成功跳过，因此 x = 7 是可行的。

可以证明不存在更小的 x。