작업 일상

브리가디르 파벨은 유럽 건축가들이 설계한 최신 프로젝트에 따라 콘서트홀을 짓는 작업반을 이끌고 있다. 건물의 가장 큰 특징은 정문 앞 열주로, $n$개의 기둥으로 이루어진다. 고전 건축의 관념과 달리 각 기둥은 고유한 높이를 가지며, 정문 위 지붕의 높이와 같지 않다. 현재 계획에서 기둥의 높이는 왼쪽부터 오른쪽 순서로 지붕을 기준으로 $a_1, a_2, \ldots, a_n$ 미터이다. 예를 들어 높이가 10이면 기둥이 지붕 위로 10미터 솟는다는 뜻이고, 높이가 -5이면 기둥 윗면과 지붕 사이에 5미터의 틈이 있다는 뜻이다.

인수와 개관 3일 전, 건축가들이 현장에 도착해 설계를 바꿨다. 새 요구 사항은 최근 유럽 유행을 따라 이웃한 두 기둥의 높이 차이가 모두 같아야 한다는 것이다. 즉 1부터 $n - 1$까지의 모든 정수 $i$, $j$에 대해 $a_{i+1} - a_i = a_{j+1} - a_j$가 성립해야 한다. 각 기둥의 정확한 높이는 상관없다. 기술적인 이유로 기둥 높이는 지붕을 기준으로 한 정수 미터여야 한다.

기둥 높이를 $x$미터 올리거나 내리면 $x$부를의 비용이 든다. 파벨은 요구 사항을 만족하면서 높이 변경에 드는 총비용을 최소로 하도록 각 기둥의 새 높이를 골라 달라고 부탁한다. 그를 도와주지 않으면 그는 다시는 외국 설계의 건물을 짓자는 초대를 받지 못하게 된다.

첫 줄에 건물 앞 기둥의 개수를 나타내는 정수 $n$ ($2 \leq n \leq 3\,000\,000$)이 주어진다.

둘째 줄에는 현재 기둥의 높이를 나타내는 정수 $n$개 $a_1, a_2, \ldots, a_n$ ($-10^9 \leq a_i \leq 10^9$)이 주어진다.

최적 계획에서 첫 번째 기둥의 높이와 이웃한 기둥 사이의 높이 차이, 두 정수를 출력한다.

출력하는 두 수의 절댓값은 모두 $10^{16}$을 넘지 않아야 한다. 이 조건을 만족하는 최적 답이 존재한다고 보장된다.

첫 번째 테스트에서는 기둥이 두 개뿐이라 자동으로 요구 사항을 만족하므로 높이를 바꿀 필요가 없다.

두 번째 테스트의 최적 기둥 높이는 3, 7, 11, 15, 19이며, 총비용은 $|3 - 3| + |7 - 8| + |11 - 10| + |15 - 13| + |19 - 20| = 5$이다.