흥미로운 분할

배열의 부분배열이란 배열의 연속한 일부를 말한다. 배열을 부분배열로 분할한다는 것은 배열 전체를 겹치지 않게 덮는 부분배열들의 모임을 뜻한다. 즉 배열의 각 원소는 정확히 하나의 부분배열에 속한다. 예를 들어 배열 A = [3, 1, 4, 1, 5]에 대해 [3, 1, 4]와 [1, 5]는 A의 부분배열 분할이지만, [3, 4, 5]는 A의 부분배열이 아니다.

정수 배열과 그 배열을 공집합이 아닌 부분배열로 나눈 분할이 주어졌을 때, 각 부분배열의 비용은 그 부분배열의 최댓값으로 정의하고, 분할 전체의 비용은 각 부분배열 비용의 합으로 정의한다.

예를 들어 배열 [3, 5, 7, 1, 2, 4]를 생각하자. 부분배열 [3, 5], [7], [1, 2, 4]로 이루어진 분할의 비용은 5 + 7 + 4 = 16이고, 부분배열 [3], [5, 7, 1], [2, 4]로 이루어진 분할의 비용은 3 + 7 + 4 = 14이다. 두 분할 모두 k = 3개의 부분배열로 이루어져 있지만 비용은 다르다. 다른 분할들은 또 다른 비용을 가질 수 있다.

N개의 정수로 이루어진 배열 A와 1 ≤ k ≤ N인 정수 k가 주어졌을 때, A를 공집합이 아닌 k개의 부분배열로 나누는 모든 분할의 집합 P(A, k)를 생각하자. P(A, k)에서의 최소 비용을 구할 수 있는가? 최대 비용도 구할 수 있는가? 모든 k에 대해? 그렇다면 해 보자.

첫째 줄에 배열 A의 원소 개수 N (1 ≤ N ≤ 8000)이 주어진다. 둘째 줄에 배열을 나타내는 N개의 정수 A1, A2, . . . , AN (1 ≤ Ai ≤ 109, i = 1, 2, . . . , N)이 주어진다.

N개의 줄을 출력한다. k번째 줄에는 P(A, k)에서의 최소 비용과 최대 비용을 나타내는 두 정수를 순서대로 출력한다.