import java.util.*;
public class Main {
public static void main
(String[] args
) { Scanner scanner
= new Scanner
(System.
in); int n = scanner.nextInt();
int[] b = new int[n + 1];
for (int i = 1; i <= n; i++) {
b[i] = scanner.nextInt();
}
int[][] dp = new int[n + 1][5];
// rech first pos forwaard only
dp[1][1] = b[1];
// cant rech first index with back jump from 2nd
// its alr visited
// CANT REACH 2ND POS WITH forward jumps
// take cost to reach dp[i-1][1] that is the forward jumps to reach i-1
// b[3] taken coz we alr need to be at 3 if we can get to 2, IMP :: and the cost at b[3] is dp[1][1]
// that is forward jumps from dp[i-1][1] since that forward jump from i-1 to i+1 is what lets us be at i + 1
// finally take the back jump from i+1.. this is the cost of being at i coming from back jump
dp[2][2] = b[3] + b[2] + dp[1][1];
int i = 3;
while (i <= n-1) {
dp
[i
][1] = b
[i
] + Math.
min(dp
[i
- 2][1], dp
[i
- 2][2]); dp[i][2] = b[i] + b[i + 1] + dp[i - 1][1];
i++;
}
//At n-1 point, the loop has calculated: dp[n-1][1], dp[n-1][2]
// now for n, we cant come back to n .. either we reach n or we can skip n
// if we reached n-1 thru back and took n value then we jump straight out
//take min of
dp
[i
][2] = b
[n
] + Math.
min(dp
[i
-2][2],dp
[i
-2][1]); dp[i][1] = 100000000 ;
dp[n][2],
Math.
min(dp
[n
- 1][1], dp
[n
- 1][2]) );
}
}
aW1wb3J0IGphdmEudXRpbC4qOwoKcHVibGljIGNsYXNzIE1haW4gewoKICAgIHB1YmxpYyBzdGF0aWMgdm9pZCBtYWluKFN0cmluZ1tdIGFyZ3MpIHsKICAgICAgICBTY2FubmVyIHNjYW5uZXIgPSBuZXcgU2Nhbm5lcihTeXN0ZW0uaW4pOwogICAgICAgIGludCBuID0gc2Nhbm5lci5uZXh0SW50KCk7CgogICAgICAgIGludFtdIGIgPSBuZXcgaW50W24gKyAxXTsKICAgICAgICBmb3IgKGludCBpID0gMTsgaSA8PSBuOyBpKyspIHsKICAgICAgICAgICAgYltpXSA9IHNjYW5uZXIubmV4dEludCgpOwogICAgICAgIH0KCiAgICAgICAgaW50W11bXSBkcCA9IG5ldyBpbnRbbiArIDFdWzVdOwogICAgICAgIC8vIHJlY2ggZmlyc3QgcG9zIGZvcndhYXJkIG9ubHkKICAgICAgICBkcFsxXVsxXSA9IGJbMV07CiAgICAgICAgLy8gY2FudCByZWNoIGZpcnN0IGluZGV4IHdpdGggYmFjayBqdW1wIGZyb20gMm5kCiAgICAgICAgLy8gaXRzIGFsciB2aXNpdGVkCiAgICAgICAgZHBbMV1bMl0gPSBJbnRlZ2VyLk1BWF9WQUxVRTsKICAgICAgICAvLyBDQU5UIFJFQUNIIDJORCBQT1MgV0lUSCBmb3J3YXJkIGp1bXBzCiAgICAgICAgZHBbMl1bMV0gPSBJbnRlZ2VyLk1BWF9WQUxVRTsKICAgICAgICAvLyB0YWtlIGNvc3QgdG8gcmVhY2ggZHBbaS0xXVsxXSB0aGF0IGlzIHRoZSBmb3J3YXJkIGp1bXBzIHRvIHJlYWNoIGktMQogICAgICAgIC8vIGJbM10gdGFrZW4gY296IHdlIGFsciBuZWVkIHRvIGJlIGF0IDMgaWYgd2UgY2FuIGdldCB0byAyLCBJTVAgOjogYW5kIHRoZSBjb3N0IGF0IGJbM10gaXMgZHBbMV1bMV0KICAgICAgICAvLyB0aGF0IGlzIGZvcndhcmQganVtcHMgZnJvbSBkcFtpLTFdWzFdIHNpbmNlIHRoYXQgZm9yd2FyZCBqdW1wIGZyb20gaS0xIHRvIGkrMSBpcyB3aGF0IGxldHMgdXMgYmUgYXQgaSArIDEgCiAgICAgICAgLy8gZmluYWxseSB0YWtlIHRoZSBiYWNrIGp1bXAgZnJvbSBpKzEuLiB0aGlzIGlzIHRoZSBjb3N0IG9mIGJlaW5nIGF0IGkgY29taW5nIGZyb20gYmFjayBqdW1wCiAgICAgICAgZHBbMl1bMl0gPSBiWzNdICsgYlsyXSArIGRwWzFdWzFdOwoKICAgICAgICBpbnQgaSA9IDM7CiAgICAgICAgd2hpbGUgKGkgPD0gbi0xKSB7CiAgICAgICAgICAgIGRwW2ldWzFdID0gYltpXSArIE1hdGgubWluKGRwW2kgLSAyXVsxXSwgZHBbaSAtIDJdWzJdKTsKICAgICAgICAgICAgZHBbaV1bMl0gPSBiW2ldICsgYltpICsgMV0gKyBkcFtpIC0gMV1bMV07CiAgICAgICAgICAgIGkrKzsKICAgICAgICB9CiAgICAgICAgLy9BdCBuLTEgcG9pbnQsIHRoZSBsb29wIGhhcyBjYWxjdWxhdGVkOiBkcFtuLTFdWzFdLCBkcFtuLTFdWzJdCiAgICAgICAgLy8gbm93IGZvciBuLCB3ZSBjYW50IGNvbWUgYmFjayB0byBuIC4uIGVpdGhlciB3ZSByZWFjaCBuIG9yIHdlIGNhbiBza2lwIG4gIAogICAgICAgIC8vIGlmIHdlIHJlYWNoZWQgbi0xIHRocnUgYmFjayBhbmQgdG9vayBuIHZhbHVlIHRoZW4gd2UganVtcCBzdHJhaWdodCBvdXQKICAgICAgICAvL3Rha2UgbWluIG9mIAogICAgICAgIGRwW2ldWzJdID0gYltuXSArIE1hdGgubWluKGRwW2ktMl1bMl0sZHBbaS0yXVsxXSk7CiAgICAgICAgZHBbaV1bMV0gPSAxMDAwMDAwMDAgOyAKICAgICAgICBpbnQgYW5zID0gTWF0aC5taW4oCiAgICAgICAgICAgICAgICBkcFtuXVsyXSwKICAgICAgICAgICAgICAgIE1hdGgubWluKGRwW24gLSAxXVsxXSwgZHBbbiAtIDFdWzJdKQogICAgICAgICk7ICAgIAogICAgICAgIFN5c3RlbS5vdXQucHJpbnQoYW5zKTsKICAgIH0KfQo=