В Долине муми-троллей в ряд стоят несколько домов, в которых живёт семья Муми-троллей и их друзья. Каждый дом имеет свою высоту. Приближается весна, и все жители решили провести большую генеральную уборку, которая включает также и уборку крыши.
Единственная проблема заключается в том, что каждому жителю понадобится лестница, чтобы добраться до своей крыши. Они могут использовать лестницу, чтобы подняться с земли на крышу любого из домов, чья высота не превышает длину лестницы. Оказавшись на крыше, они могут перебираться на соседнюю крышу слева или справа, при условии, что высота этой соседней крыши отличается от высоты крыши, на которой они находятся, не более, чем на длину лестницы, которую они взяли. Можно делать несколько переходов на соседнюю крышу, если для этого хватает длины лестницы.
Помогите каждому из жильцов определить минимальную высоту лестницы, которая ему понадобится, чтобы добраться до своей крыши.
В первой строке дано одно целое число $$$n$$$ ($$$1 \le n \le 100\,000$$$) — количество домов в Муми-доле.
Во второй строке даны $$$n$$$ целых чисел $$$a_i$$$ ($$$1 \le a_i \le 10^9$$$) — высоты домов.
Выведите $$$n$$$ целых чисел $$$l_i$$$ — минимальную длину лестницы, с помощью которой можно забраться на крышу $$$i$$$-го домика.
4 3 4 2 6
2 2 2 4
9 3 4 1 6 4 2 5 1 3
3 3 1 2 2 2 3 1 2
В первом тесте в Муми-доле четыре дома разной высоты: первый дом, в котором живет семья Муми-троллей, имеет высоту 3 метра, второй дом, принадлежащий Снусмумрику, имеет высоту 4 метра, третий дом, где живет Малышка Мю, имеет высоту 2 метра, а четвёртый дом, где живет Фрёкен Снорк, имеет высоту 6 метров.
Малышке Мю понадобится двухметровая лестница, и она воспользуется ей, чтобы попасть прямо с земли на крышу своего маленького дома. Снусмумрику также понадобится только двухметровая лестница. Сначала он использует её, чтобы добраться до крыши Малышки Мю, а потом с неё заберётся на собственную крышу. Такая же лестница понадобится и семье Муми-троллей: двухметровой лестницы будет достаточно, чтобы попасть сначала на крышу Малышки Мю, затем на крышу Снусмумрика. А оттуда они, используя лестницу, смогут спустить на один метр вниз, на собственную крышу. Фрёкен Снорк, в то же время, понадобится 4-метровая лестница. Сначала она воспользуется ей, чтобы добраться до крыши Малышки Мю, а затем с неё поднимется и на свою.
| ВКОШП.Junior - 2023. Финал |
|---|
| Закончено |
