В Берляндии есть особый туристический маршрут — Золотое кольцо. Этот маршрут состоит из $$$n$$$ городов и циклического железнодорожного маршрута. Города пронумерованы от $$$1$$$ до $$$n$$$ таким образом, что:

• следующим городом для $$$1$$$ является город $$$2$$$;
• следующим городом для $$$2$$$ является город $$$3$$$;
• ...
• следующим городом для $$$n$$$ является город $$$1$$$.

Таким образом, маршрут замкнут в цикл, города пронумерованы по ходу движения (маршрут — односторонний).

Блогер Поликарп хочет начать своё путешествие в городе $$$1$$$. Про каждый город он знает величину $$$a_i$$$ — сколько селфи он хочет сделать в $$$i$$$-м городе. За одно посещение города он может сделать там не более одного селфи. Так как он едет на поезде, то города он пропускать не может (он всегда перемещается из города $$$i$$$ в город $$$i+1$$$ для $$$1 \le i < n$$$ и из $$$n$$$ в $$$1$$$). Таким образом, когда поезд останавливается в городе, то Поликарп обязательно посещает этот город. Если Поликарп посещает город многократно, то все посещения учитываются отдельно.

Какое наименьшее количество посещений городов придётся Поликарпу совершить, чтобы выполнить свой план по количеству селфи для каждого города? Учтите, что первым он всегда посещает город $$$1$$$, так как именно в этом городе начинается его путешествие.