Battery Balancing

You are given n batteries with various power units. You can redistribute the power among the batteries in any manner (by transferring integer units) in order to minimize the difference between the highest and the lowest charged batteries.

Mathematically, if the total power is \(S\) and there are \(n\) batteries, the optimal equal distribution is \(\lfloor S/n \rfloor\) units for some batteries and \(\lfloor S/n \rfloor + 1\) units for the others. The minimum possible difference after redistribution will be 0 if \(S\) is divisible by \(n\), and 1 otherwise.

Your task is to determine this minimum difference.

inputFormat

The first line contains a single integer \(n\) denoting the number of batteries.

The second line contains \(n\) space-separated integers, where each integer represents the power units of a battery.

outputFormat

Output a single integer which is the minimum possible difference between the highest and the lowest battery charge after an optimal redistribution.

3
1 6 3

1