농부 Nhoj는 Bessie를 아무것도 없는 한가운데에 떨어뜨렸다! 시간 t = 0에 Bessie는 무한한 수직선 위의 x = 0에 위치해 있다. Bessie는 출구를 찾기 위해 매 초마다 왼쪽 또는 오른쪽으로 1만큼 이동하며 필사적으로 움직인다. 하지만 실제로는 출구가 없고, T초가 지난 후 Bessie는 다시 x = 0으로 돌아와 지치고 체념하게 된다.

농부 Nhoj는 Bessie의 이동 경로를 추적하려 하지만, x = 0.5, 1.5, 2.5, \dots, (N-1).5를 몇 번씩 통과했는지만 알고 있다. 이 정보는 배열
A_0, A_1, \dots, A_{N-1}로 주어진다.

Bessie는 x > N이거나 x < 0인 위치에는 절대 도달하지 않는다.

특히, Bessie의 이동 경로는 길이가 T = \sum_{i=0}^{N-1} A_i 인 문자열로 표현할 수 있으며, 각 문자는 L 또는 R이다. i번째 문자는 Bessie가 i번째 초에 이동한 방향을 나타낸다.

방향 전환 횟수는 문자열에서 부분 문자열 LR이 나타나는 횟수와 RL이 나타나는 횟수의 합으로 정의된다.

농부 Nhoj를 도와, 배열 A와 일치하면서 방향 전환 횟수를 최소화하는 Bessie의 가능한 이동 경로 하나를 찾아라. 그러한 경로가 최소 하나 이상 존재함은 보장된다.

1 \le N \le 10^5
1 \le A_i \le 10^6
\sum A_i \le 10^6

#5471 upload 30 done 11 how_to_reg 9 auto_awesome スペシャルジャッジ

Moo Route timer 1s memory 32MB

#5471
スペシャルジャッジ

Moo Route 1s 32MB