Equal towers

Problem Statement

Equal towers Problem Description You are given an array A of N integers, indexed from 0 . Two kinds of operations are available, and each one moves a single unit between two neighbouring elements: Choose an index i with 0 <= i <= N - 2 and A[i] > A[i+1] , then decrease A[i] by 1 and increase A[i+1] by 1 . Choose an index i with 0 <= i <= N - 2 and A[i] < A[i+1] , then increase A[i] by 1 and decrease A[i+1] by 1 . In both cases one unit is transferred from the larger of the two neighbours to the smaller one. Neighbours that are already equal cannot be chosen. Determine the minimum number of operations needed to make every element of A equal. Because that count can be very large, report it modulo 1000000007 . If no sequence of operations can make all elements equal, report -1 instead. Input Format The first line contains a single integer N , the number of elements in A . Each of the next N lines contains a single integer; the line at position i ( 0 <= i < N ) hold