Street Trees

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.

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.

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