5112. 青蛙游戏

单点时限: 1.0 sec

内存限制: 128 MB

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

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

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

输入格式

输入共两行。

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

输出格式

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

样例

Input
3 5
2 5 8
Output
17
Input
4 3
2 2 4 6
Output
12

提示

样例#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 的青蛙离佩奇初始位置最远。

166 人解决,196 人已尝试。

175 份提交通过,共有 412 份提交。

2.5 EMB 奖励。

创建: 9 月,1 周前.

修改: 9 月,1 周前.

最后提交: 1 周,3 天前.

来源: N/A

题目标签