Дан неориентированный граф из $$$n$$$ вершин и $$$n-1$$$ ребер. Вес $$$i$$$-го ребра равен $$$a_i$$$; это ребро соединяет вершины $$$i$$$ и $$$i+1$$$.

Изначально в каждой вершине расположена фишка. Число, написанное на фишке в $$$i$$$-й вершине, равно $$$i$$$.

За одну операцию можно выбрать фишку (если в какой-то вершине находится несколько фишек, то можно выбрать любую, но только одну) и передвинуть ее по ребру. Стоимость такой операции равна весу ребра.

Стоимостью графа назовем минимальную стоимость такой последовательности операций, что:

• после того, как все операции произведены, в каждой вершине ровно одна фишка, и число на каждой фишке не равно номеру вершины, в которой она находится.

Вы должны обработать $$$q$$$ запросов:

• $$$k$$$ $$$x$$$ — изменить вес $$$k$$$-го ребра (соединяющего вершины $$$k$$$ и $$$k+1$$$) на $$$x$$$.

После каждого запроса выведите стоимость графа. Обратите внимание, что на самом деле вы не перемещаете фишки, только считаете стоимость графа; при каждом подсчете фишки расположены в исходных позициях.