스위치

시간 제한1초메모리 제한1024 MB

요약

스위치를 누른 시각의 점수와 그 다음 두 초의 점수를 2배로 만들되 세 초의 재사용 대기 시간을 두고, 얻을 수 있는 점수의 최댓값을 구한다.

난이도: 보통10점 중 5점
유형: 동적 계획법, 그리디
정답자: 아직 제출이 없습니다

문제

$i$ 초에 $A\_i$ 의 점수를 얻는 게임이 있다. $N$ 초 동안 진행하는 이 게임에서는 점수를 추가로 얻기 위해 $T$ 초에 스위치를 눌러 $T,T+1,T+2$ 초에 얻는 점수를 $2$ 배로 만들 수 있다. $T$ 초에 스위치를 누르면 $T+3$ 초부터 다시 스위치를 누를 수 있다.

게임이 진행되는 동안 스위치를 적절하게 눌렀을 때 얻을 수 있는 점수의 최댓값을 구해보자.

입력

첫째 줄에 점수를 얻는 횟수 $N$ 이 주어진다. $\left( 3\leq N\leq 200\\, 000 \right)$

둘째 줄에 $i$ 초에 얻는 점수를 나타내는 정수 $A\_i$ 가 공백으로 구분되어 주어진다. $\left( 1\leq i\leq N;\ |A\_i|\leq 1\\, 000 \right)$

출력

얻을 수 있는 점수의 최댓값을 출력한다.

예제4

예제 1
입력
```
3
-2 0 1
```
예상 출력
```
0
```
예제 2
입력
```
4
1 2 3 4
```
예상 출력
```
20
```
예제 3
입력
```
5
-1 -2 -3 -4 -5
```
예상 출력
```
-15
```
예제 4
입력
```
9
-2 10 2 -7 9 1 -2 -3 4
```
예상 출력
```
34
```