Битоническая подпоследовательность
Последовательность чисел 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 должны выполняться неравенства 1 ≤ i_1 ≤ i_2 ≤ ... ≤ i_k ≤ n.
Ваша задача состоит в том, чтобы написать программу, которая найдет битоническую подпоследовательность заданной последовательности, для которой максимальна сумма цифр входящих в нее чисел. При этом предполагается, что числа записываются в десятичной системе счисления.
Входные данные
Первая строка входного файла содержит целое число n (3 ≤ n ≤ 1000). Вторая строка входного файла содержит n целых чисел a_1, ..., a_n - заданную последовательность. Для каждого из них верны неравенства 1 ≤ a_i ≤ 10^9.
Выходные данные
В первой строке выходного файла выведите сумму цифр чисел, входящих в найденную битоническую подпоследовательность. Если у заданной последовательности нет битонических подпоследовательностей, выведите в выходной файл число -1.