10168번 - 파발마 서브태스크

조선시대에는 임금님에게 상소문을 보낼 때 말을 이용하여 상소문을 전달하였고 이를 파발마라고 불렀다. 파발마들은 지방의 역에서 관리되었고 한 지방역에서 파발마를 이용하여 다른 지방역으로 상소문을 전달하면 다른 지방역에서 파발마를 이용하여 또 다른 지방역으로 상소문을 전달하는 식으로 몇 개의 지방역을 거쳐서 한양역까지 전달하는 것이다. 

조선에는 전국에 N 개의 지방역이 있고 이 역들과 한양역을 모두 연결하는 N+1 개의 도로가 원모양으로 연결되어 있다. 따라서 각 역들은 항상 2개의 역과 인접한다. 한양역이 원형의 꼭대기에 있는 것으로 가정하고 각 지방역은 한양역에서 시계방향으로 1번부터 시작하여 번호가 붙은 것으로 생각한다. 아래 그림은 N=5인 경우의 예이다.

상소문은 하루에 인접한 역으로만 이동할 수 있으며 이동하지 않고 머물러 있는 것도 가능하다. 위의 그림처럼 어느 날 역 3에 상소문이 있으면 그 다음날에는 역 2이나 역 4로 이동할 수 있으며 역 3에 머물러 있는 것도 가능하다. 한 역에 여러 개의 상소문이 함께 모여 있을 수 있으며 한 마리의 파발마로 여러 개의 상소문을 한꺼번에 이동하는 것도 가능하다. 

여러분은 어떤 날 지방역들의 상태를 받게 된다. 각 지방역은 하나의 상소문을 가지고 있거나 없거나 둘 중 하나의 상태이다. 이 상소문을 한양역으로 보내야 하는데, 말 한 마리를 하루 사용하면 상소문 개수에 상관없이 1냥의 비용이 든다. 그리고 상소문마다 비용이 발생하는데 하나의 상소문이 한양역까지 이동하는데 D일이 걸리면 D냥의 비용이 든다. 이때 처음이나 중간에 머무르는 날도 한양역으로 이동하는 날에 포함된다. 

위의 그림의 경우 역 3에 있는 상소문을 역 2로 먼저 이동한 후에 두 상소문을 함께 역 2에서 역 1로 그리고 한양역으로 이동하는 경우의 비용을 계산해 보자. 먼저 첫날 역 3의 상소문을 역 2로 이동하기 위해 파발마 1마리를 사용하고 다음날 역 2의 상소문 2개를 역 1로 이동하기 위해 파말마 1마리를 사용한다. 3일째에는 역 1의 상소문 2개를 한양역으로 이동하기 위해 파발마 1마리를 사용한다. 결론적으로 총 3일 동안 매일 한 마리의 파발마를 사용하므로 3냥의 비용이 들고 두 개의 상소문이 한양역에 도착하는데 3일씩 걸리므로 6냥의 비용이 필요하여 총 9냥의 비용이 든다. 

여러분은 지방역의 수와 각 지방역의 상태를 입력 받아서 모든 상소문을 한양역으로 전달하는 데 필요한 최소의 비용을 출력하는 프로그램을 작성하라. 말은 모든 지방역에 충분히 많이 있다고 가정한다.

입력의 첫 줄에는 지방역의 수 N (3 ≤ N ≤ 1,000,000)이 주어진다. 다음 줄에는 숫자 N개가 주어지는데 1번 역부터 순서대로, 그 역에 상소문이 있는 경우에는 1이, 없는 경우에는 0이 공백을 사이에 두고 주어진다. 

출력은 단 한 줄이며, 최소 비용을 정수로 출력한다. 비용의 값이 커질 수 있으므로 64비트 정수 변수 (long long)를 사용해야 할 수도 있음에 주의하라.