Bytica має каменів розташованих по колу, з вартістю a_1, a_2, \dots, a_n. Вона хоче забрати деякі з каменів щоб зробити оптимальне намисто без зміни їх відносного порядку.
Зауважте, що оптимальне намисто можна поділити на 3 послідовні частини , , , де
складається з каменів з незменшуючимися вартостями,
це один діамант. (Діамант це камінь з вартістю )
складається з каменів з незбільшуючимися вартостями.
Знайдіть максимальну загальну вартість каменів у оптимальному намисті.
Перший рядок містить одне ціле (1 \leq n \leq 10^5).
Другий рядок містить цілих a_1, a_2, ..., a_n — вартості каменів (0 \leq a_i \leq 10000, 1 \leq \text{кількість діамантів} \leq 10).
Надрукуйте цiле, що задає максимальну вартiсть каменів у оптимальному намисті.
Приклад 1
Приклад 2