408309: GYM103091 I Pipes

Stanford's unofficial mascot is the Tree! Each year, a secret ritual is held in Main Quad in order to honor the holiness of the Tree. During this ritual, $$$N$$$ trees are placed in a circle, each with varying height. The students gather inside of this circle and complete the ritual. However, last year the secret was spilled and made its way across the Bay to Berkeley's campus. The Berkeley students, being jealous that their mascot is just a bear, decided that they wanted to sabotage this auspicious ritual.

The Stanford Engineering students found out about this plot, and came up with a plan to prevent the Berkeley attack. They discovered that if they were able to make all of the trees in the circle the same height, then they could deploy an electronic barrier that prevents Berkeley Bears from entering campus.

It was a genius plan, but they needed to figure out how to make all of the trees the same height without killing the trees! Luckily, they were able to create a very complicated device that looked just like a pipe. The specifications of this device are too advanced to include in the description section of this problem. These pipes had the capability of transforming matter. In particular, if placed between two adjacent trees, a pipe was able to open a matter portal that averaged the heights of the two trees! This portal will never close, which means that if additional pipes are added, expanding the amount of trees that are connected, all of their values are averaged together.

More concretely, consider having three trees $$$A$$$, $$$B$$$ and $$$C$$$ in a circle, with heights 10, 20, and 3 respectively. If a pipe was added between trees $$$A$$$ and $$$B$$$ the resulting heights of the trees would be [15, 15, 3]. If now an additional pipe was added between trees $$$B$$$ and $$$C$$$ the trees' heights would be [11, 11, 11].

These pipes are really time consuming and expensive to make, so the Stanford Engineers want to use as few as possible. They need your help. Given $$$N$$$ numbers representing the initial heights of all of the trees, output the minimum number of pipes needed to be added between adjacent trees, such that the resulting heights of all trees are equal. It is guaranteed that the resulting height is an integer.

The first line contains a single integer $$$N$$$ ($$$ 1 \leq N \leq 5 \cdot 10^5$$$). The second line contains $$$N$$$ integers $$$a_i$$$ ($$$ 1 \leq a_i \leq 10^9$$$) representing the starting heights of the trees. Trees $$$i = 1$$$ and $$$i = N$$$ are adjacent to each other in the circle.

Output a single integer, which is the minimum number of pipes needed to be added to the trees such that the resulting heights of all trees are equal.

6
6 6 1 7 10 6

2

3
5 5 5

0