Дан неориентированный граф из \(n\) вершин и \(n-1\) ребер. Вес \(i\)-го ребра равен \(a_i\); это ребро соединяет вершины \(i\) и \(i+1\).
Изначально в каждой вершине расположена фишка. Число, написанное на фишке в \(i\)-й вершине, равно \(i\).
За одну операцию можно выбрать фишку (если в какой-то вершине находится несколько фишек, то можно выбрать любую, но только одну) и передвинуть ее по ребру. Стоимость такой операции равна весу ребра.
Стоимостью графа назовем минимальную стоимость такой последовательности операций, что:
- после того, как все операции произведены, в каждой вершине ровно одна фишка, и число на каждой фишке не равно номеру вершины, в которой она находится.
Вы должны обработать \(q\) запросов:
- \(k\) \(x\) — изменить вес \(k\)-го ребра (соединяющего вершины \(k\) и \(k+1\)) на \(x\).
После каждого запроса выведите стоимость графа. Обратите внимание, что на самом деле вы не перемещаете фишки, только считаете стоимость графа; при каждом подсчете фишки расположены в исходных позициях.