Minimum Coins Transfer on a Circular Table

There are \( n \) people sitting around a circular table. Each person has a certain number of coins and the total number of coins is divisible by \( n \). Each person is allowed to transfer some coins to his immediate neighbors (both left and right) in order to eventually equalize the number of coins each person has.

Let the coins each person has be \( a_0, a_1, \dots, a_{n-1} \) and the total sum \( S = \sum_{i=0}^{n-1} a_i \). Since \( S \) is divisible by \( n \), the target number of coins for each person is \( T = \frac{S}{n} \). Define \( d_i = a_i - T \). One can show that if we compute the cumulative differences as \( f_0 = 0 \) and for \( 1 \le i \le n-1 \), \( f_i = \sum_{j=0}^{i-1} d_j \), then the minimum total number of coins that need to be transferred is given by:

\( \text{Answer} = \sum_{i=0}^{n-1} \left| f_i - m \right| \)

where \( m \) is the median of the sequence \( \{ f_0, f_1, \dots, f_{n-1} \} \). Your task is to compute and output this minimum total coins transferred.

inputFormat

The first line contains an integer \( n \) (the number of people). The second line contains \( n \) space-separated integers \( a_0, a_1, \dots, a_{n-1} \) representing the number of coins each person initially has. It is guaranteed that \( \sum_{i=0}^{n-1} a_i \) is divisible by \( n \).

outputFormat

Output a single integer, the minimum total number of coins that must be transferred so that everyone ends up with \( \frac{\sum_{i=0}^{n-1} a_i}{n} \) coins.

sample

3
1 2 3

1