Make Necklace Optimal#12834

Make Necklace Optimal

1 секунда
512 мегабайтів
Складна

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

Loading
Loading

Приклад 2

Loading
Loading