[ABC024B] 自動ドア

# AT1336 自动门 ## 题目描述 ABC市场是高桥王国最受欢迎的超市。超市入口是一扇自动门。当一个人从门前经过时，自动门会自动打开，一直打开T秒，然后自动关闭。当一个人在门打开时通过，时间会增加T秒。 今天，N位顾客在自动门前走过。第i个人经过的时间是Ai。求今天自动门打开的总秒数。 ## 输入输出格式 ###### 输入格式：像下面一样。 N T A1 A2 … AN 第1行:整数N（1≤N≤10^5），表示今天通过自动门的人数和整数T（1≤T≤10^5），表示门持续开的时间。 2到N+1行：客户在自动门之前经过的时间Ai（1≤Ai≤10^6）。 A1≤A2≤…≤AN 成立。 ###### 输出格式：1行，输出门打开的秒数。在输出的末尾添加换行符。 ## 说明 50%的数据满足 1≤T≤100 100%的数据满足 1≤T≤10^5

[problemUrl]: https://atcoder.jp/contests/abc024/tasks/abc024_b ABCマーケットは高橋王国で最も人気なスーパーマーケットです。 入り口は自動ドアになっています。 この自動ドアは人が前を通りかかると自動で開き、そこから $ T $ 秒後まで開き続け、その後自動的に閉じます。 ドアが開いている状態で新たに人が前を通りかかると、通りかかった時刻のさらに $ T $ 秒後まで開き続ける時間が延長されます。 今日はのべ $ N $ 人の客が自動ドアの前を通りかかりました。 $ i $ 番目の人が通りかかった時刻はABCマーケットが開店してから $ A_i $ 秒経った時刻です。 今日、この自動ドアが開いていた合計秒数を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ T $ $ A_1 $ $ A_2 $ : $ A_N $ - $ 1 $ 行目に今日自動ドアの前を通りかかった人数を表す整数 $ N(1\ ≦\ N\ ≦\ 10^5) $ とドアが開き続ける時間を表す整数 $ T(1\ ≦\ T\ ≦\ 10^5) $ が空白区切りで与えられる。 - $ 2 $ 行目からの $ N $ 行のうち $ i $ 行目には $ i $ 番目の客が自動ドアの前を通りかかった時刻 $ A_i(1\ ≦\ A_i\ ≦\ 10^6) $ が与えられる。 - $ A_1\ ≦\ A_2\ ≦\ …\ ≦\ A_N $ が成り立つ。

ドアが開いていた秒数を $ 1 $ 行に出力せよ。 出力の末尾に改行を入れること。

5 10
20
100
105
217
314

45

10 10
1
2
3
4
5
6
7
8
9
10

19

10 100000
3
31
314
3141
31415
314159
400000
410000
500000
777777

517253

### 部分点 この問題には部分点が設定されている。 - $ 1\ ≦\ T\ ≦\ 100 $を満たすデータセットに正解した場合は $ 50 $ 点が与えられる。 - $ 1\ ≦\ T\ ≦\ 10^5 $を満たすデータセットに正解した場合はさらに $ 50 $ 点が与えられる。合計で$ 100 $点となる。 ### Sample Explanation 1 時刻が $ 20 $ ～ $ 30 $、$ 100 $ ～ $ 115 $、$ 217 $ ～ $ 227 $、$ 314 $ ～ $ 324 $ のときにドアが開いています。