Максимальне щастя

Обмеження: 2 сек., 256 МіБ

Кожен святкує свято 47-го дня року по-своєму. Дехто зустрічається зі своїми друзями і влаштовує гучну забаву. Дехто запускає гучні феєрверки. Дехто сидить і розв’язує святкові задачки.

Пан Дмитро з нагоди свята вирішив поласувати спеціальним святковим набором цукерок. Набір складається з \(n\) цукерок. Кожна цукерка має свій рівень щастя — ціле число 4 або 7. Усі цукерки розташовані в ряд, так що в кожної цукерки окрім першої і останньої є рівно два сусіди.

Особливість цього набору така, що з’їдаючи певну цукерку, рівень щастя їдуна збільшується на сумарний рівень щастя двох сусідів цукерки, яку він з’їдає. Зауважимо, що з’їдати першу або останню цукерку з набору заборонено.

Пан Дмитро хоче з’їсти всі цукерки крім першої і останньої так, щоб досягнути максимального щастя. Допоможіть йому визначити якого найбільшого рівня щастя він може досягнути.

Вхідні дані

У першому рядку задано одне ціле число \(n\) — кількість цукерок у наборі.

У другому рядку задано \(n\) цілих чисел \(a_i\) — рівні щастя цукерок у тому порядку, у якому вони розташовані в наборі.

Вихідні дані

У єдиному рядку виведіть одне ціле число — максимальний рівень щастя, який можна досягнути.

Обмеження

7 тестів: \(3 \le n \le 20\),

15 тестів: \(3 \le n \le 100\),

25 тестів: \(3 \le n \le 10^5\),

\(a_i \in \{4, 7\}\).

Приклади