408935: GYM103384 3 Андрей и порталы

Андрей вот-вот опоздает на школьный этап ВсОШ. К счастью, недавно в его городе появились порталы.

Город, в котором живет Андрей, можно представить в виде прямой. Всего в городе успели построить $$$N$$$ порталов. Портал с номером $$$i$$$ расположен в точке с координатой $$$x_i$$$. Если в текущий момент времени вы находитесь в одной точке с каким-нибудь порталом, то можете всего за одну секунду телепортироваться в любой другой портал вне зависимости от расстояния между ними. А время, требуемое для преодоления расстояния между точками с координатами $$$p$$$ и $$$q$$$ без использования порталов равно $$$\lvert p - q \rvert$$$ секунд. Андрей является влиятельным гражданином, поэтому он может использовать систему порталов любое количество раз.

Изначально Андрей находится в точке $$$s$$$, а точка проведения олимпиады имеет координату $$$e$$$. Помогите Андрею понять, как быстро он может попасть на олимпиаду, ведь каждая секунда на счету.

В первой строке входных данных записано одно целое число $$$s$$$ — начальное положение Андрея.

Во второй строке записано одно целое число $$$e$$$ — место проведения олимпиады.

В третьей строке записано количество порталов $$$N$$$ ($$$2 \le N \le 2 \cdot 10^5$$$).

В каждой из $$$N$$$ следующих строк записано целое число $$$x_i$$$ — координата портала с номером $$$i$$$.

Все числа $$$s$$$, $$$e$$$, $$$x_i$$$ по модулю не превосходят $$$10^8$$$.

Выведите одно число — минимальное количество секунд, которое потребуется Андрею для того, чтобы добраться до места проведения олимпиады.

Решения, правильно работающие только для случаев, когда $$$N$$$ не превосходит $$$10$$$, будут оцениваться в $$$20$$$ баллов.

Решения, правильно работающие только для случаев, когда $$$N$$$ не превосходит $$$1\,000$$$, будут оцениваться в $$$60$$$ баллов.

0
4
3
1
3
5

3

Рассмотрим пример из условия.

Если бы Андрей не мог пользоваться порталами, он бы смог добраться до точки проведения олимпиады за $$$\lvert 0 - 4 \rvert = 4$$$ секунды. Однако, можно действовать так:

1. Дойти до портала с номером $$$1$$$ за $$$\lvert 0 - 1 \rvert = 1$$$ секунду.
2. Телепортироваться в портал с номером $$$2$$$ за одну секунду.
3. Дойти от портала с номером $$$2$$$ до точки проведения олимпиады за $$$\lvert 3 - 4 \rvert = 1$$$ секунду.

Суммарно получаем $$$1 + 1 + 1 = 3$$$ секунды.