졸린 소 몰기 (Silver)

면접 대비

시간 제한2초메모리 제한512 MB

요약

수직선 위에 있는 N마리 소의 위치가 주어질 때, 맨 바깥의 소만 옮겨 연속된 정수 위치에 모으는 최소 및 최대 이동 횟수를 구합니다.

난이도: 보통10점 중 6점
유형: 정렬, 슬라이딩 윈도우, 그리디
정답자: 아직 제출이 없습니다

문제

Farmer John의 $N$ 마리 소는 늘 농장 먼 곳으로 흩어진다. 소들을 다시 모을 수 있도록 도와 달라.

농장의 main field는 길고 좁다. 이를 정수 위치에 소가 놓일 수 있는 수직선으로 생각하면 된다. $N$ 마리 소는 서로 다른 정수 위치에 있으며, Farmer John은 이 소들이 연속된 위치(예를 들어 3, 4, 5, 6, 7, 8)를 차지하도록 하려 한다.

소들은 졸려서, Farmer John은 끝점(모든 소 중 최소 또는 최대 위치에 있는 소)에 있는 소만 움직일 수 있다. 소를 움직일 때는 비어 있는 임의의 정수 위치로 보낼 수 있지만, 그 위치에서 해당 소가 더 이상 끝점이 아니어야 한다. 이런 이동이 반복되면 소들은 점점 가까워진다.

소들이 $N$ 개의 연속된 위치에 모이기까지 가능한 이동 횟수의 최솟값과 최댓값을 구하라.

입력

첫 줄에 $N$ ( $3 \leq N \leq 10^5$ )이 주어진다. 이어지는 $N$ 개의 줄에는 소 한 마리의 정수 위치가 각각 주어진다. 위치는 $1 \ldots 10^9$ 범위이다.

출력

첫 번째 줄에는 소들을 모으는 데 필요한 이동 횟수의 최솟값을 출력한다. 두 번째 줄에는 소들이 모이기 전까지 가능한 이동 횟수의 최댓값을 출력한다.

힌트

최솟값은 1이다. Farmer John이 4에 있는 소를 8로 옮기면 소들은 7, 8, 9에 연속으로 놓인다.

최댓값은 2이다. 예를 들어 9에 있는 소를 6으로 옮기고, 이어서 7에 있는 소를 5로 옮길 수 있다.

예제1

예제 1
입력
```
3
7
4
9
```
예상 출력
```
1
2
```