Штаб гражданской обороны Тридесятой области решил обновить план спасения на случай ядерной атаки. Известно, что все селений Тридесятой области находятся вдоль одной прямой дороги. Вдоль дороги также расположены бомбоубежищ, в которых жители селений могут укрыться на случай ядерной атаки. Чтобы спасение в случае ядерной тревоги проходило как можно эффективнее, необходимо для каждого селения определить ближайшее к нему бомбоубежище. В первой строке вводится число — количество селений (1

Данная задача сводится к нахождению ближайшего бомбоубежища для каждого селения. Мы можем решить ее с помощью алгоритма двух указателей.

Шаги решения:
1. В первую очередь, нам нужно создать отсортированный список координат бомбоубежищ.
2. Затем мы пройдемся по каждому селению и будем искать ближайшее бомбоубежище с помощью двух указателей.
3. У нас будет два указателя — один указывающий на предыдущее бомбоубежище (инициализируется как первое бомбоубежище) и один указывающий на следующее бомбоубежище (инициализируется как второе бомбоубежище).
4. Мы будем двигать эти два указателя в зависимости от расстояния между текущим селением и ближайшими бомбоубежищами.
5. Если расстояние от текущего селения до предыдущего бомбоубежища меньше расстояния от текущего селения до следующего бомбоубежища, то текущее бомбоубежище становится ближайшим для текущего селения. Иначе, следующее бомбоубежище становится ближайшим.
6. Повторяем шаги 4-5 для каждого селения.
7. Выводим результаты — ближайшее бомбоубежище для каждого селения.

Алгоритм работает за линейное время O(N+M), где N – количество селений, M – количество бомбоубежищ. Это оптимальное решение для данной задачи.