시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 116 53 49 45.794%

문제

가톨릭대학교 축제에 N개의 시식코너가 열렸다.

최대한 많은 양의 음식을 먹고 싶은 아리는 방문한 시식코너에 남아있는 가능한 모든 음식들을 먹으려 한다. 하지만 연속으로 3개의 시식코너를 방문하면 눈치가 보이기 때문에 이럴 경우 최소 1번은 시식을 하지 않고 시식코너를 지나가야 한다. 예를 들어 1번과 2번 시식코너에서 시식했으면 2번 연속으로 시식했기 때문에 3번 시식코너는 방문할 수 없다.

아리는 식욕에 비해 장이 약해 잘 체하기 때문에 연속해서 시식할 경우 연속된 시식코너 중 2번째 시식코너에서는 그 시식코너에서 제공하는 총 음식 개수의 1/2개밖에 먹지 못한다. 단 음식의 개수가 홀수일 경우 음식의 개수를 2로 나누었을 때 몫만큼의 음식만 먹을 수 있다.

올해 가톨릭대학교 축제에는 사람들이 많이 몰렸기 때문에 음식이 0개인 시식코너가 있을 수 있다. 축제에서 진행하는 총 시식코너의 개수와 각 시식코너에서 시식할 수 있는 음식의 개수가 주어졌을 때 아리가 먹을 수 있는 음식의 최대 개수를 구하여라.

입력

첫째 줄에 시식코너의 개수 N이 주어진다(1 ≤ N ≤ 100,000) 둘째 줄부터 N+1번째 줄까지 각 시식코너에서 제공하는 음식의 개수가 순서대로 주어진다. 음식의 개수는 1,000이하의 음이 아닌 정수이다.

출력

첫째 줄에 아리가 최대로 먹을 수 있는 음식의 개수를 출력한다.

예제 입력 1

6
1
2
4
3
2
2

예제 출력 1

8

예제 입력 2

8
5
6
2
1
4
5
3
2

예제 출력 2

16