Круглий амбар (Бронза)#10581
Будучи прихильником сучасної архітектури, Фермер Джон побудував новий корівник у формі ідеального кола. Всередині корівник складається з кільця з кімнат, пронумерованих за годинниковою стрілкою від до по периметру корівника. Кожна кімната має двері, що з'єднують її з двома сусідніми кімнатами, а також двері, що ведуть назовні з корівника.
Фермер Джон хоче, щоб у кожній кімнаті опинилося рівно r_i корів. Щоб організовано загнати корів у корівник, він планує відкрити зовнішні двері рівно однієї кімнати, через які корови зможуть увійти. Потім кожна корова рухається за годинниковою стрілкою через кімнати, поки не досягне свого місця призначення. Фермер Джон хоче вибрати такі зовнішні двері, щоб мінімізувати сумарну відстань, пройдену всіма коровами. Визначте мінімальну сумарну відстань, яку повинні пройти корови, якщо він вибере оптимальні двері. Відстань, пройдена однією коровою, визначається як кількість внутрішніх дверей, через які вона проходить.
У першому рядку міститься ціле число n~(3 \le n \le 1000). У наступних рядках міститься по одному цілому числу r_i~(1 \le r_i \le 100).
Виведіть мінімальну сумарну відстань, яку повинні пройти всі корови.
У цьому прикладі оптимальним рішенням є впустити корів через зовнішні двері кімнати, в якій потрібно розмістити корів.
Приклад 1