파발마

조선시대에는 임금에게 상소문을 올릴 때 말을 이용해 상소문을 전달했고, 이 말을 파발마라고 불렀다. 파발마는 지방의 역에서 관리했다. 한 지방역에서 파발마로 다른 지방역까지 상소문을 옮기고, 그 역에서 다시 파발마로 또 다른 역까지 옮기는 식으로 여러 역을 거쳐 한양역까지 전달한다.

조선에는 지방역이 $N$개 있고, 이 역들과 한양역을 모두 잇는 도로 $N + 1$개가 원 모양을 이룬다. 따라서 모든 역은 항상 두 역과 인접한다. 한양역이 원의 꼭대기에 있다고 보고, 지방역에는 한양역에서 시계 방향으로 1번부터 차례로 번호를 붙인다. 아래 그림은 $N = 5$인 경우다.

상소문은 하루에 인접한 역으로만 옮길 수 있고, 옮기지 않고 그 역에 머무르는 것도 가능하다. 위 그림처럼 어느 날 역 3에 상소문이 있으면 다음 날 역 2나 역 4로 옮길 수 있고, 역 3에 그대로 둘 수도 있다. 한 역에 상소문이 여러 개 모일 수 있고, 파발마 한 마리가 여러 개를 한꺼번에 옮기는 것도 가능하다.

어느 날의 지방역 상태가 주어진다. 각 지방역은 상소문을 하나 가지고 있거나 없거나 둘 중 하나다. 이 상소문을 모두 한양역으로 보내야 한다. 말 한 마리를 하루 쓰면 실은 상소문 개수와 상관없이 1냥이 든다. 상소문마다도 비용이 붙는데, 상소문 하나가 한양역까지 가는 데 $D$일이 걸리면 $D$냥이 든다. 처음이나 중간에 머무른 날도 $D$에 포함한다.

위 그림에서 역 3의 상소문을 먼저 역 2로 옮긴 뒤, 두 상소문을 함께 역 2에서 역 1로, 다시 한양역으로 옮기는 경우의 비용을 따져 보자. 첫날 역 3의 상소문을 역 2로 옮기려고 파발마 한 마리를 쓴다. 다음 날 역 2에 모인 상소문 2개를 역 1로 옮기려고 한 마리를 쓴다. 사흘째에는 역 1의 상소문 2개를 한양역으로 옮기려고 한 마리를 쓴다. 사흘 동안 매일 한 마리씩 썼으므로 말 값이 3냥이고, 상소문 2개가 각각 사흘 만에 한양역에 닿았으므로 6냥이 더해져 모두 9냥이 든다.

지방역의 수와 각 지방역의 상태를 읽어서, 모든 상소문을 한양역까지 전달하는 데 드는 최소 비용을 출력하는 프로그램을 작성하여라. 말은 모든 지방역에 넉넉히 있다고 가정한다.

첫째 줄에 지방역의 수 $N$ ($3 \le N \le 1{,}000{,}000$)이 주어진다.

둘째 줄에 숫자 $N$개가 1번 역부터 순서대로 공백을 사이에 두고 주어진다. 그 역에 상소문이 있으면 1, 없으면 0이다.

최소 비용을 정수로 한 줄에 출력한다. 비용이 커질 수 있으므로 64비트 정수형(long long)을 써야 할 수도 있음에 주의하여라.