РОИ: 2 тур

Вдоль прямой дороги, на которой происходят испытания беспилотных грузовиков, расположены \(n\) городов, \(i\)-й город находится в точке, имеющей координату \(i\). В \(i\)-м городе установлена антенна мощностью \(a_i\), покрывающая все города от \(L_i = \max\left(1, i - a_i\right)\) до \(R_i = \min(n, i + a_i)\) включительно.

Беспилотный грузовик перемещается вдоль дороги от города \(s\) к городу \(t\), где \(s < t\). В каждом городе по пути следования грузовик подключён к одной из антенн. Подключение к антеннам происходит следующим образом.

• В начальном городе грузовик подключается к антенне, покрывающей этот город, у которой значение \(R_i\) максимально. Если таких антенн несколько, выбирается любая из них.
• После перемещения грузовика из города \(v\) в город \(v+1\), если антенна, к которой он был подключен в городе \(v\), покрывает также и город \(v+1\), грузовик остаётся подключен к этой антенне. Иначе, если антенна, к которой он был подключён, не покрывает город \(v+1\), грузовик переподключается к антенне, покрывающей город \(v+1\), для которой значение \(R_i\) максимально. Если таких антенн несколько, выбирается любая из них.

Обозначим как \(f(s, t)\) количество переподключений между антеннами для грузовика, который начинает свой маршрут в городе \(s\) и заканчивает свой маршрут в городе \(t\) (\(s < t\)). Начальное подключение к антенне в городе \(s\) переподключением не считается.

Нестойкостью покрытия дороги антеннами назовем сумму значений \(f(s, t)\) по всем допустимым парам городов, то есть величину \(\)F= \sum\limits_{s=1}^{n-1} \sum\limits_{t=s+1}^{n} f(s, t). \(\)

В распоряжении оператора дороги есть одна запасная антенна с мощностью \(x\). Для снижения нестойкости покрытия можно заменить одну из антенн на запасную. Требуется определить минимальное значение нестойкости покрытия дороги \(F\), если не более одной антенны можно заменить на запасную антенну мощности \(x\).