Sleepy Cow Herding (Silver)

Interview

Time limit2sMemory limit512 MB

Summary

Find the minimum and maximum moves to make N cows on a number line occupy consecutive integers, moving only the leftmost or rightmost cow each turn.

Level: Medium6 of 10
Topics: Sorting, Sliding window, Greedy
Solved: No attempts yet

Problem

Farmer John's $N$ cows are always wandering off to the far reaches of the farm! He needs your help herding them back together.

The main field is long and skinny. Think of it as a number line, where a cow can occupy any integer location. The $N$ cows are at different integer locations, and Farmer John wants them to occupy consecutive locations (for example 3, 4, 5, 6, 7, and 8).

The cows are sleepy, so Farmer John can only move a cow if she is an endpoint (the minimum or maximum position among all cows). When he moves a cow, he can send her to any unoccupied integer location, as long as she is no longer an endpoint there. Over time these moves push the cows closer together.

Determine the minimum and maximum number of moves possible before the cows are grouped in $N$ consecutive locations.

Input

The first line contains $N$ ( $3 \leq N \leq 10^5$ ). Each of the next $N$ lines contains the integer location of one cow, in the range $1 \ldots 10^9$ .

Output

The first line is the minimum number of moves Farmer John needs to group the cows together. The second line is the maximum number of moves he could make before the cows are grouped together.

Hint

The minimum number of moves is 1. If Farmer John moves the cow at 4 to 8, the cows are at consecutive locations 7, 8, 9.

The maximum number of moves is 2. For example, the cow at 9 could be moved to 6, and then the cow at 7 could be moved to 5.

Examples1

Example 1
Input
```
3
7
4
9
```
Expected output
```
1
2
```