eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Битоническая подпоследовательность

Битоническая подпоследовательность

Лимит времени 2 секунды
Лимит использования памяти 64 MiB

Последовательность чисел b_1, b_2, ..., b_m называется битонической, если существует такое число j (1< j < m), что выполняются неравенства b_1 < b_2 < ... < b_j > b_{j+1} > ... > b_m. Заметим, что в соответствии с этим определением, битоническая последовательность должна содержать хотя бы три элемента.

Пусть задана некоторая последовательность чисел a_1, a_2, ..., a_n. Ее подпоследовательностью называется последовательность следующего вида:

a_i1, a_i2, ..., a_ik

При этом для чисел i_1, ..., i_k должны выполняться неравенства 1i_1i_2 ≤ ... ≤ i_kn.

Ваша задача состоит в том, чтобы написать программу, которая найдет битоническую подпоследовательность заданной последовательности, для которой максимальна сумма цифр входящих в нее чисел. При этом предполагается, что числа записываются в десятичной системе счисления.

Входные данные

Первая строка входного файла содержит целое число n (3n1000). Вторая строка входного файла содержит n целых чисел a_1, ..., a_n - заданную последовательность. Для каждого из них верны неравенства 1a_i10^9.

Выходные данные

В первой строке выходного файла выведите сумму цифр чисел, входящих в найденную битоническую подпоследовательность. Если у заданной последовательности нет битонических подпоследовательностей, выведите в выходной файл число -1.

Пример

Входные данные #1
4
2 1 3 1
Выходные данные #1
6