Круглий амбар (Золото)

Будучи прихильником сучасної архітектури, Фермер Джон побудував новий корівник у формі ідеального кола. Всередині корівник складається з кільця з $n$ кімнат, пронумерованих за годинниковою стрілкою від $1$ до $n$ по периметру корівника. Кожна кімната має двері, що з'єднують її з двома сусідніми кімнатами, а також двері, що ведуть назовні з корівника.

Фермер Джон володіє $n$ коровами і хоче, щоб у кожній кімнаті корівника опинилося рівно по одній корові. Однак корови, будучи трохи розгубленими, вишикувалися біля випадкових дверей, причому біля одних і тих самих дверей може перебувати кілька корів. Рівно c_i корів вишикувалися зовні дверей кімнати $i$, тому \sum c_i = n.

Щоб організувати процес заганяння корів так, щоб у кожній кімнаті опинилося рівно по одній корові, Фермер Джон використовує такий підхід: кожна корова заходить через двері, біля яких вона спочатку стояла в черзі, а потім рухається за годинниковою стрілкою через кімнати, поки не досягне свого місця призначення. Якщо корова проходить через $d$ дверей, вона витрачає d^2 одиниць енергії. Визначте мінімальну сумарну кількість енергії, необхідну для розподілу корів таким чином, щоб у кожній кімнаті опинилося рівно по одній корові.