Соня решила, что лучше всего зарабатывать деньги, имея отельный бизнес, так как можно и прибыль получить, и отдыхать где захочется.
Страна, в которой живет Соня, представляет собой бесконечную прямую. В каждой целочисленной координате на этой прямой находится город. У девочки есть $$$n$$$ отелей, $$$i$$$-й отель находится в городе с координатой $$$x_i$$$. Соня — девочка умная, поэтому, она не открывает два или более отеля в одном городе.
Соня понимает, что в бизнесе нужно расширяться, открывая новые отели, поэтому, она решила построить еще один. Она хочет, чтобы расстояние от нового отеля до ближайшего другого отеля было равно $$$d$$$. Девочка понимает, что есть много возможных вариантов постройки такого отеля. По этой причине для начала она хочет узнать количество возможных координат городов, в которых она может построить новый отель.
Так как Соня занята тем, что лежит в джакузи в одном из ее отелей, она просит вас найти количество городов, где она может построить новый отель так, чтобы расстояние от него до ближайшего из $$$n$$$ заданных отелей было в точности равно $$$d$$$.
Первая строка содержит два целых числа $$$n$$$ и $$$d$$$ ($$$1\leq n\leq 100$$$, $$$1\leq d\leq 10^9$$$) — количество отелей Сони и требуемое расстояние от нового отеля до ближайшего.
В следующей строке записана строго возрастающая последовательность из $$$n$$$ различных чисел $$$x_1, x_2, \ldots, x_n$$$ ($$$-10^9\leq x_i\leq 10^9$$$) — координаты отелей Сони.
Выведите количество городов, в которых Соня может построить новый отель так, чтобы расстояние до ближайшего другого отеля было равно $$$d$$$.
4 3
-3 2 9 16
6
5 2
4 8 11 18 19
5
В первом примере есть $$$6$$$ возможных городов, где можно построить новый отель, эти города имеют координаты: $$$-6$$$, $$$5$$$, $$$6$$$, $$$12$$$, $$$13$$$ и $$$19$$$.
Во втором примере можно построить отель в $$$5$$$ возможных городах, которые имеют координаты: $$$2$$$, $$$6$$$, $$$13$$$, $$$16$$$ и $$$21$$$.
| Codeforces Round 495 (Div. 2) |
|---|
| Закончено |
