Balance the Bookshelves

There are \(n\) bookshelves arranged in a circle. The first bookshelf is followed by the second, the second by the third, and so on. The \((n-1)\)-th bookshelf is followed by the \(n\)-th bookshelf, and the \(n\)-th bookshelf is followed by the first bookshelf. The \(i\)-th bookshelf has \(b_i\) books.

To enhance the library's aesthetic appeal, WZF and ShenNiu have tasked SY with redistributing the books so that every bookshelf has an equal number of books. However, because there may be many books to move, SY can only move books between adjacent bookshelves.

Determine the minimum number of book movements required to achieve an equal distribution. It is guaranteed that the total number of books is divisible by \(n\).

inputFormat

The first line contains a single integer \(n\) \( (1 \leq n \leq 10^5) \), representing the number of bookshelves. The second line contains \(n\) integers \(b_1, b_2, \dots, b_n\) \( (0 \leq b_i \leq 10^9) \), where \(b_i\) denotes the number of books on the \(i\)-th bookshelf.

outputFormat

Output a single integer: the minimum number of books that need to be moved so that every bookshelf has the same number of books.

sample

3
1 2 3

1