Туристы, достопримечательности и телескопы

Заметим, что при увеличении силы, количество видных достопримечательностей из города строго возрастает. Поэтому можно для каждого города запустить бинарный поиск по ответу. Для того, чтобы быстро пересчитать сумму на отрезке $$$[l;r]$$$, можно использовать префикс-суммы.

Пусть $$$p_i$$$ — сумма $$$s_j$$$ с $$$1$$$-го по $$$i$$$-й. Для удобства положим $$$p_0 = 0$$$. Тогда если у $$$i$$$-го города поставить силу телескопа $$$x$$$, из него будет видно $$$p_{min(i + x, n)} - p_{max(i - x - 1, 0)}$$$ достопримечательностей.