공 떨어뜨리기

표준 좌표평면 위에 공 $n$개와 구멍 $n$개가 있다. 어떤 높이 $h > 0$에 대해 공은 $(1, h), (2, h), \dots, (n, h)$ 위치에 놓여 있고, 구멍은 $(1, 0), (2, 0), \dots, (n, 0)$ 위치에 있다. 어느 순간 모든 공이 동시에 아래로($y$축의 음의 방향으로) 떨어지기 시작한다. 공이 $i$번 구멍에 들어가면 $c_i$점을 얻는다.

아무것도 하지 않으면 공 $i$는 구멍 $i$로 떨어져 총점은 $c_1 + c_2 + \dots + c_n$이 된다. 결과를 바꾸려면 정확히 하나의 장애물을 설치해야 하며, 장애물은 서로 다른 두 정수 열을 잇는 선분이다.

• 오른쪽 장애물은 $x_1, x_2 \in \mathbb{N}$, $1 \le x_1 < x_2 \le n$, $h > y_1 > y_2 > 0$을 만족하는 선분 $(x_1, y_1) - (x_2, y_2)$이다(오른쪽으로 기울어져 오른쪽 끝이 더 낮다).
• 왼쪽 장애물은 $x_1, x_2 \in \mathbb{N}$, $1 \le x_1 < x_2 \le n$, $0 < y_1 < y_2 < h$를 만족하는 선분 $(x_1, y_1) - (x_2, y_2)$이다(왼쪽으로 기울어져 왼쪽 끝이 더 낮다).

떨어지던 공이 선분에 닿으면 잠시 멈춘 뒤 선분의 낮은 쪽 끝으로 미끄러져 내려가고, 마지막으로 그 낮은 끝 바로 아래의 구멍으로 곧장 떨어진다. 열 번호가 $[x_1, x_2]$ 범위에 있는 모든 공이 장애물에 걸린다. 따라서 오른쪽 장애물은 공 $x_1, x_1 + 1, \dots, x_2$를 모두 구멍 $x_2$로 보내고, 왼쪽 장애물은 공 $x_1, x_1 + 1, \dots, x_2$를 모두 구멍 $x_1$로 보낸다. 장애물을 설치하면 여러 공이 들어간 구멍과 하나도 없는 구멍이 생길 수 있지만, 모든 공은 여전히 어떤 구멍엔가 들어간다.

다음 두 질문에 답하라.

• 오른쪽 장애물을 정확히 하나 설치해야 할 때 얻을 수 있는 최고 점수는 얼마인가?
• 왼쪽 장애물을 정확히 하나 설치해야 할 때 얻을 수 있는 최고 점수는 얼마인가?

첫째 줄에 공의 개수(구멍의 개수와 같다) $n$이 정수로 주어진다. 둘째 줄에 왼쪽부터 오른쪽 순서로 구멍의 값 $c_1, c_2, \dots, c_n$이 공백으로 구분되어 주어진다.

두 줄을 출력한다. 첫째 줄에는 오른쪽 장애물을 정확히 하나 설치해야 할 때의 최고 점수를 정수 하나로 출력한다. 둘째 줄에는 왼쪽 장애물을 정확히 하나 설치해야 할 때의 최고 점수를 정수 하나로 출력한다. 답은 32비트 정수 범위를 벗어날 수 있으므로 64비트 정수 자료형을 사용해야 한다.

• $3 \le n \le 300\,000$.
• $-10^9 \le c_i \le 10^9$.

$c = [6, 10, -7, 2, 5, -12]$인 예제를 보자. 가장 좋은 오른쪽 장애물은 공 3, 4, 5번을 잡아 구멍 5로 보내며 $6 + 10 + 5 + 5 + 5 + (-12) = 19$점을 준다. 가장 좋은 왼쪽 장애물은 공 2번부터 6번까지 잡아 구멍 2로 보내며 $6 + 10 + 10 + 10 + 10 + 10 = 56$점을 준다. 다른 어떤 배치도 이보다 높은 점수를 낼 수 없다. 장애물 설치는 필수이므로, 모든 배치가 불리할 때는 필수 선분 때문에 총점이 오히려 낮아질 수 있다.