Є \(N\) магазинів розташованих на кільцевій дорозі (так що наступним після магазину номер \(N\) є магазин номер \(1\)). В кожному магазині є певна кількість товарів.

Перевезення 1 товару в сусідній (наступний або попередній) магазин коштує 1 гривню (відповідно перевезення 1 товару на два магазини вперед коштує 2 гривні, і т.д.)

Необхідно визначити, за яку найменшу ціну можна досягти того, що в усіх магазинах буде однакова кількість товарів (гарантується що це можливо).

Формат вхідних даних

В першому рядку число \(N\) - кількість магазинів (\(1 \le N \le 100\)).
В другому рядку \(N\) цілих чисел \(Ai\) - кількість товарів у відповідному магазині (\(1 \le Ai \le 100\)).

Формат вихідних даних

Виведіть найменшу ціну, за яку можна рівномірно розподілити товари по магазинах

Приклад вхідних даних

5
17 9 14 16 4

Приклад вихідних даних

11