An array of size N is given. In one operation we can add 1 to element at index i and subtract 1 from element at index j. (i!=j).

Using this operation we have to minimize the difference between maximum and minimum array elements and print minimum no. of operations required to achieve this minimum difference.

E.g. N=2, A=[1,6] -> Answer is 2.
     Steps : [1,6] -> [2,5] -> [3,4] (This is minimum difference configuration that we can achieve]

E.g. N=5, A=[1,2,3,4,5]-> Answer is 3.
     Steps : [1,2,3,4,5] -> [2,2,3,4,4] -> [3,2,3,4,3] -> [3,3,3,3,3] (This is minimum difference configuration].

Constraints : 

N<=10^5, Array elements <= 10^4

I tried by taking the sum of elements and then taking the average and making each element equal to average but didn't work out. Then thought to apply binary search to find minimum possible difference value but couldn't come up with any good implementation regarding how to apply binary search here.

Please suggest some approach for solving this problem. Thanks in advance :)