提莫攻击

题目描述

在《英雄联盟》的世界中，有一个叫“提莫”的英雄。他的攻击可以让敌方英雄艾希进入中毒状态。

给你一个非递减整数数组 timeSeries，其中 timeSeries[i] 表示提莫在 timeSeries[i] 秒时对艾希发起攻击，另给一个整数 duration 表示中毒持续时间。

当提莫在时刻 t 发起攻击后，艾希会在时间区间 [t, t + duration - 1] 内处于中毒状态。

如果提莫在中毒影响结束前再次发动攻击，中毒状态持续时间将被重置。

请返回艾希处于中毒状态的总秒数。

输入格式

第一行输入一个整数 n，表示攻击次数。

第二行输入 n 个整数，表示数组 timeSeries。

第三行输入一个整数 duration。

输出格式

输出一个整数，表示总中毒秒数。

数据范围

1 <= timeSeries.length <= 10^4

0 <= timeSeries[i], duration <= 10^7

timeSeries 按非递减顺序排列。

样例 1

输入

2
1 4
2

输出

4

样例 2

输入

2
1 2
2

输出

3