10억 이하의 자연수로 구성된, 길이 N짜리 배열이 있다.

성윤이는 이 배열에 구멍을 총 N번 뚫을 것이다. ( 한 번 구멍을 뚫은 곳에 또 뚫을 수는 없다. )

성윤이가 구멍을 한 번 뚫을 때마다, 여러분은 구멍 사이사이의 연속 구간의 숫자의 합 중 최댓값을 출력해야 한다.

연속 구간이 하나도 없다면, 0 을 출력한다.

예를 들어, N = 5 이고, 배열이 [ 7, 10, 5, 7, 8 ] 이라고 하자.

성윤이가 구멍을 뚫는 순서는 { 3, 1, 4, 2, 5 } 라고 주어졌다고 하자.

3 번째 칸에 구멍을 뚫으면 배열은 [ 7, 10, ■, 7, 8 ] 이다. 연속 구간은 2개고, 첫 번째 연속 구간은 합은 7 + 10 = 17, 두 번째 연속 구간의 합은 7 + 8 = 15 이다. 최댓값은 17 이다.

1 번째 칸에 구멍을 뚫으면 배열은 [ ■, 10, ■, 7, 8 ] 이다. 연속 구간은 2개고, 각 연속 구간의 합은 10, 15 이다. 최댓값은 15 이다.

4 번째 칸에 구멍을 뚫으면 배열은 [ ■, 10, ■, ■, 8 ] 이다. 연속 구간은 2개고, 각 연속 구간의 합은 10, 8 이다. 최댓값은 10 이다.

2 번째 칸에 구멍을 뚫으면 배열은 [ ■, ■, ■, ■, 8 ] 이다. 이제 연속 구간은 1개 뿐이고, 최댓값은 8 이다.

5 번째 칸에 구멍을 뚫으면 배열은 [ ■, ■, ■, ■, ■ ] 이다. 연속 구간은 없고, 최댓값은 0 이다.

따라서 이 경우,

17

15

10

8

0

을 출력하면 된다.

배열에 구멍 뚫기 timer 1s memory 256MB

배열에 구멍 뚫기 1s 256MB