Equal Sleep Log Transformation

Bessie the cow is notorious for falling asleep in Farmer John's class, and her classmate Elsie has been keeping track of the number of times Bessie naps during each of the N class periods. The log is represented by an array a where the i-th element a_i denotes the number of times Bessie fell asleep during the i-th period. It is known that \(1 \le N \le 10^5\), \(0 \le a_i \le 10^6\), and \(\sum_{i=1}^{N} a_i \le 10^6\).

Elsie wants to modify the log to make it appear that Bessie fell asleep exactly the same number of times in every class period. The only operation allowed is to combine two adjacent class periods into a single period (i.e. replace two consecutive numbers with their sum). After a sequence of such operations, the log will consist of several segments, and if all the segment values are equal then Elsie will succeed.

Formally, if the final log has m segments each with a value of \(T\) then we must have \(m \times T = \sum_{i=1}^{N} a_i\), and each segment must be a contiguous subsequence of the original log whose sum is \(T\). Each combination reduces the length of the log by 1. Determine the minimum number of modifications (combinations) Elsie needs to perform so that all the numbers in the log become equal.

inputFormat

Input Format:

• The first line contains an integer N (\(1 \le N \le 10^5\)), the number of class periods.
• The second line contains N space-separated non-negative integers a₁, a₂, \dots, a_N (\(0 \le a_i \le 10^6\)) with \(\sum a_i \le 10^6\).

outputFormat

Output Format:

• Output a single integer representing the minimum number of modifications required so that all elements in the log are equal.

sample

5
1 2 3 4 5

4