Valid Array

Interview

Time limit2sMemory limit128 MB

Summary

Given a distinct integer array, find the minimum number of elements to add so it contains five consecutive integers.

Level: Medium4 of 10
Topics: Array, Brute force, Implementation
Solved: No attempts yet

Problem

An integer array is valid if it contains five elements that become five consecutive integers after sorting. In other words, among those five selected values, every adjacent difference after sorting is 1.

For example, the array {6, 1, 9, 5, 7, 15, 8} is valid because it contains 5, 6, 7, 8, 9.

Given an array, determine the minimum number of new elements that must be added so that the array becomes valid.

Input

The first line contains N, the size of the array. N is a positive integer at most 50. Each of the next N lines contains one element of the array. Each element is a nonnegative integer at most 1,000,000,000, and no two elements are equal.

Output

Print the minimum number of elements that must be added so that the given array becomes valid.

Examples4

Example 1
Input
```
3
5
6
7
```
Expected output
```
2
```
Example 2
Input
```
6
5
7
9
8492
8493
192398
```
Expected output
```
2
```
Example 3
Input
```
4
1000
2000
3000
4000
```
Expected output
```
4
```
Example 4
Input
```
7
6
1
9
5
7
15
8
```
Expected output
```
0
```