#XXSY26JBT3. 红军搭浮桥

红军搭浮桥

红军搭浮桥

题目描述

红军工兵连搭建了一座秘密浮桥。这座浮桥的设计非常特殊:

1 开启机制:当一名红军战士踏上浮桥时,浮桥会立即进入“稳固通行状态”。

2 自动隐蔽:当一名红军战士踏上浮桥时,浮桥维持 d秒的稳固时间。d 秒后为了安全,浮桥会自动沉入水下隐蔽。

3 计时重置:如果浮桥在通行状态下,又有一名战士踏了上来,浮桥的稳固计时器会立即重置,从这一刻起重新计算 d 秒后再隐蔽。

现在共有 n 名战士陆续通过了浮桥,他们踏上桥的时间点分别是 t1,t2,…,tnt_1,t_2,…,t_n。请你计算,从第一名战士踏上浮桥开始,到最后浮桥自动隐蔽,浮桥总共在水面上开启了多少时间?

输入格式

第一行:两个正整数 n 和 d*。*n 表示通过浮桥的战士人数,d表示浮桥的稳固时间。

第二行:n个单调不降的正整数 t1,t2,…,tnt_1,t_2,…,t_n,表示每位战士踏上浮桥的时间点。

输出格式

一行一个整数,表示浮桥位于通行状态的总时间。

输入输出样例

7 3
1 2 7 10 15 17 22
18

7 5
1 2 7 10 15 17 22
26

数据规模与约定

对于 100%的数据:1≤n≤105,1≤ti≤109,且t1≤t2≤t3≤⋯≤tn,1≤d≤1091≤n≤10^5,1≤ti≤10^9,且 t_1≤t_2≤t_3≤⋯≤t_n,1≤d≤10^9。