Bitonic Subsequence#636
A sequence of numbers b_1, b_2, \ldots, b_m is called bitonic if there exists an index (1 < j < m) such that b_1 < b_2 < \ldots < b_j > b_{j+1} > \ldots > b_m. According to this definition, a bitonic sequence must contain at least three elements.
Suppose you are given a sequence of numbers a_1, a_2, \ldots, a_n. A subsequence of this sequence is a sequence of the form:
a_{i_1}, a_{i_2}, \ldots, a_{i_k}
where the indices i_1, \ldots, i_k satisfy 1 \leq i_1 < i_2 < \ldots < i_k \leq n.
Your task is to write a program that finds a bitonic subsequence of the given sequence such that the sum of the digits of the numbers in this subsequence is maximized. The numbers are represented in the decimal system.
The first line of the input contains an integer (3 \leq n \leq 1000). The second line contains integers a_1, \ldots, a_n, the given sequence. For each a_i, 1 \leq a_i \leq 10^9.
Output the maximum sum of the digits of the numbers in a bitonic subsequence found. If there is no bitonic subsequence in the given sequence, output .
Example 1