Problem #5112 - ECNU Online Judge

单点时限: 1.0 sec

内存限制: 128 MB

一条马路上趴着很多青蛙，佩奇正好非常无聊，打算逗弄一下这些青蛙作为打发时间的游戏。她站在笔直的马路上，她的前方趴着 $N$ 只青蛙（可以看作一条直线上有 $N$ 只青蛙），这些青蛙的编号从近到远依次为 $1, 2, \dots, N$ 。每只青蛙的初始位置与佩奇的距离是已知的，从近到远分别为 $A_{1}, A_{2}, \dots, A_{N}$ 。可能有多只青蛙与佩奇的距离相同。佩奇从最初的位置一直向前走，经过奇数只青蛙的时候会逗弄一下这只青蛙，这只青蛙受到惊吓会向前跳 $D$ 米，路过偶数只青蛙的时候什么也不做（没有被逗弄的青蛙不会移动）。重复这个过程直到佩奇前方没有青蛙，到此游戏结束。

需要注意一只青蛙向前跳跃后，佩奇继续往前走还会遇到它，由于佩奇记不清前面是否已遇到过这只青蛙，这只青蛙会被当成尚未遇见的并重复计数，因此一只青蛙可能会被逗弄多次。当佩奇经过的一个位置同时趴着多只青蛙时，佩奇会将这些青蛙按照初始编号排序，初始编号小的看做离自己更近。

现在佩奇想要知道游戏结束时，离佩奇初始位置最远的青蛙与佩奇初始位置的距离是多少。

输入格式

输入共两行。

第一行包含 $2$ 个由空格分隔的正整数，分别表示青蛙的数量 $N (1 \leq N \leq 10^{5})$ 和青蛙受到惊吓后跳跃的距离 $D (1 \leq D \leq 10^{9})$ 。第二行包含 $N$ 个由空格分隔的正整数，从左到右分别为 $A_{1}, A_{2}, \dots, A_{N} (1 \leq A_{1} \leq A_{2} \leq \dots \leq A_{N} \leq 10^{9})$ ，分别表示 $N$ 只青蛙的初始位置与佩奇初始位置的距离。

输出格式

输出是一个整数，表示游戏结束时，离佩奇初始位置最远的青蛙与佩奇初始位置的距离。

样例

Input

3 5
2 5 8

Output

Input

4 3
2 2 4 6

Output

提示

样例#1 总共有 3 只青蛙，一只青蛙受惊吓后会向前跳跃 5 米，初始状态下青蛙离佩奇的初始位置距离分别为 2、5、8 米。初始青蛙位置: 2 5 8。

佩奇向前走，第 1 次经过的青蛙位置为 2，她逗弄了这只青蛙，青蛙受到惊吓向前跳跃了 5 米，位置变为 7，另外 2 只青蛙位置不变，第一次逗弄后佩奇初始位置从近到远的青蛙位置变为：5 7 8。

佩奇继续向前走，第 2 次经过的青蛙位置为 5，她什么也没有做，青蛙位置不变。

佩奇第 3 次经过的青蛙位置为 7，她逗弄了这只青蛙，青蛙受到惊吓向前跳跃了 5 米，位置变为 12。3 只青蛙位置变为：5 8 12。

第 4 次经过的青蛙位置为 8，她什么也没有做。

佩奇第 5 次经过的青蛙位置为 12，她逗弄了这只青蛙，青蛙向前跳跃了 5 米，位置变为 17。3 只青蛙位置变为：5 8 17。

第 6 次经过的青蛙位置为 17，她什么也没有做。

至此，佩奇前方没有青蛙了，游戏结束，当前位置为 17 的青蛙离佩奇初始位置最远。

168 人解决，201 人已尝试。

177 份提交通过，共有 450 份提交。

2.6 EMB 奖励。

创建: 1 年，11 月前.

修改: 1 年，11 月前.

最后提交: 1 月前.

来源: N/A

5112. 青蛙游戏

输入格式

输出格式

样例

提示

服务

开源

关于我们