Relay Horses

In the Joseon dynasty a petition to the king traveled by horse, and that horse was called a relay horse. Relay horses were kept at provincial stations. One provincial station carries a petition by horse to another provincial station, that station carries it on to the next one, and after several stations the petition reaches the capital station in Hanyang.

Joseon has $N$ provincial stations, and $N + 1$ roads join those stations and the capital station into a circle. Every station is therefore adjacent to exactly two stations. Place the capital station at the top of the circle and number the provincial stations from 1 upward, going clockwise from the capital station. The picture below shows the case $N = 5$.

A petition moves to an adjacent station in one day, and it may also stay where it is for a day. In the picture, a petition that sits at station 3 on some day can move to station 2 or to station 4 the next day, or stay at station 3. Several petitions can gather at one station, and a single relay horse can carry several petitions at once.

You are given the state of the provincial stations on some day. Each provincial station holds one petition or none. All of these petitions have to reach the capital station. Using one horse for one day costs 1 nyang, whatever the number of petitions it carries. Each petition costs money as well: if a petition takes $D$ days to reach the capital station, it costs $D$ nyang. Days on which the petition stays put, at the start or in the middle, count toward $D$.

Take this plan for the picture and add up its cost. Move the petition at station 3 to station 2, then carry both petitions from station 2 to station 1, then from station 1 to the capital station. On the first day one relay horse moves the petition at station 3 to station 2. On the second day one horse moves the two petitions gathered at station 2 to station 1. On the third day one horse moves the two petitions at station 1 to the capital station. One horse a day for three days costs 3 nyang, and the two petitions each need three days to reach the capital station, which adds 6 nyang, so the plan costs 9 nyang in total.

Read the number of provincial stations and the state of each one, then print the smallest cost of delivering every petition to the capital station. Assume every provincial station has plenty of horses.

The first line contains the number of provincial stations $N$ ($3 \le N \le 1{,}000{,}000$).

The second line contains $N$ numbers, given in order from station 1 and separated by spaces. A number is 1 when that station holds a petition and 0 when it does not.

Print the smallest cost as an integer on one line. The cost can grow large, so a 64-bit integer type (long long) may be needed.