Бітонічна підпослідовність#636
Послідовність чисел b_1, b_2, \ldots, b_m називається бітонічною, якщо існує індекс (1 < j < m) такий, що b_1 < b_2 < \ldots < b_j > b_{j+1} > \ldots > b_m. За цим визначенням, бітонічна послідовність повинна містити щонайменше три елементи.
Нехай вам задана послідовність чисел a_1, a_2, \ldots, a_n. Підпослідовністю цієї послідовності називається послідовність виду:
a_{i_1}, a_{i_2}, \ldots, a_{i_k}
де індекси i_1, \ldots, i_k задовольняють 1 \leq i_1 < i_2 < \ldots < i_k \leq n.
Ваше завдання — написати програму, яка знаходить бітонічну підпослідовність заданої послідовності таку, що сума цифр чисел у цій підпослідовності є максимальною. Числа задано у десятковій системі числення.
Перший рядок вхідних даних містить ціле число (3 \leq n \leq 1000). Другий рядок містить цілих чисел a_1, \ldots, a_n — задану послідовність. Для кожного a_i виконується 1 \leq a_i \leq 10^9.
Виведіть максимальну суму цифр чисел у знайденій бітонічній підпослідовності. Якщо у заданій послідовності немає бітонічної підпослідовності, виведіть .
Приклад 1