Street Trees

Interview

Time limit1sMemory limit128 MB

Summary

Given sorted tree positions, find the minimum number of trees to insert so all consecutive gaps equal the GCD of all gap sizes.

Level: Medium4 of 10
Topics: Math, Number theory, Greedy
Solved: No attempts yet

Problem

Street trees are planted along one side of a straight road, but the gaps between neighboring trees are not necessarily equal. The city wants to plant additional trees so that every neighboring gap is the same while adding as few trees as possible.

A tree's position is represented by its positive integer distance from a reference point.

For positions (1, 3, 7, 13), planting at 5, 9, and 11 makes every gap equal to 2. For positions (2, 6, 12, 18), planting at 4, 8, 10, 14, and 16 is needed to make every gap equal to 2.

Given the positions of the existing trees, compute the minimum number of new trees that must be planted between existing trees so all neighboring gaps are equal.

Input

The first line contains an integer N, the number of trees already planted. (3 ≤ N ≤ 100,000)

Each of the next N lines contains one tree position. Every position is a distinct integer from 1 to 1,000,000,000, and the positions are given in increasing order of distance from the reference point.

Output

Print the minimum number of new trees that must be planted so every neighboring gap is equal.

Examples2

Example 1
Input
```
4
1
3
7
13
```
Expected output
```
3
```
Example 2
Input
```
4
2
6
12
18
```
Expected output
```
5
```