20120번 - 호반우와 리듬게임

호반우들 사이에서는 저번달 새로 출시한 리듬게임인 호스가 유행이다. 호스는 연속된 노트를 처리할 수록 보너스 점수를 받게 되는데 그 과정은 이러하다.

1. 노트에는 점수가 정수로 매겨져있다. 하지만 호스는 다른 리듬게임과 다르게 점수가 음수일 수도 있다.
2. 호반우가 연속으로 처리한 노트의 개수를 콤보라고 하자. 노트 하나를 칠 때마다 (누적 콤보)×(현재 노트) 값이 총 점수에 추가된다.
3. 연속으로 3개의 노트를 놓치면 지금까지 얻은 점수가 0점이 되고 더 이상 점수를 얻을 수 없다.
4. 호반우는 모든 노트를 주어진 순서대로 처리해야 한다.

호반우는 모든 노트를 처리해서 풀 콤보를 받았지만 최대 점수를 받을 수 없었다. 호반우를 위해 호반우가 얻을 수 있는 최대 점수를 계산해주는 프로그램을 만들어주자!

첫째 줄에 노트 개수 N (1 ≤ N ≤ 1,000) 이 주어집니다.

둘째 줄에 공백으로 구분된 N개의 정수 a₁, a_2, ..., a_n (-10,000 ≤ a_i ≤ 10,000)가 주어지는데, i번째 정수는 i번째 노트의 점수를 나타냅니다.

호반우가 얻을 수 있는 최대 점수를 출력합니다.