Криві дзеркала

За один залп BFG-9000 знищує монстрів на трьох сусідніх балкончиках. Балкончики при цьому не руйнуються. А монстри гинуть. (N-й балкончик сусідній з першим). Після залпу монстри, які залашились живими, наносять Леоніду (головному герою роману) пошкодження — по одній одиниці кожен. Далі слідує новий залп і так до тих пір, доки всі монстри не загинуть. Потрібно визначити мінімальні пошкодження, які може отримати Леонід.

Вхідні дані

Перший рядок містить ціле число N, кількість балкончиків, на яких монстри зайняли кругову оборону (3 ≤ N ≤ 30). У другому рядку дано N цілих чисел — кількість монстрів на кожному балкончику (на кожному не менше 1 і не більше 100).

Вихідні дані

Виведіть мінімальну кількість одиниць пошкоджень.

Приклади