Bitonik altardıcıllıq#636
Bir sıra ədədlər \textbf{b}_1, \textbf{b}_2, \ldots, \textbf{b}_m bitonik adlanır, əgər elə bir indeks (1 < \textbf{j} < \textbf{m}) mövcuddur ki, \textbf{b}_1 < \textbf{b}_2 < \ldots < \textbf{b}_j > \textbf{b}_{j+1} > \ldots > \textbf{b}_m. Bu tərifə əsasən, bitonik ardıcıllıq azı üç elementdən ibarət olmalıdır.
Tutaq ki, sizə \textbf{a}_1, \textbf{a}_2, \ldots, \textbf{a}_n ardıcıllığı verilib. Bu ardıcıllığın bir altardıcıllığı aşağıdaki kimidir:
\textbf{a}_{i_1}, \textbf{a}_{i_2}, \ldots, \textbf{a}_{i_k}
burada indekslər i_1, \ldots, i_k şərtləri ödəyir: 1 \leq i_1 < i_2 < \ldots < i_k \leq n.
Sizin vəzifəniz bu verilmiş ardıcıllıq üçün elə bir bitonik altardıcıllıq tapmaqdır ki, bu altardıcıllığın ədədlərinin rəqəmləri cəminin məbləği maksimum olsun. Ədədlər onluq say sistemində verilir.
Girişin birinci sətrində bir tam ədəd (3 \leq n \leq 1000) verilir. İkinci sətirdə a_1, \ldots, a_n ədədlərindən ibarət ardıcıllıq verilir. Hər bir a_i üçün, 1 \leq a_i \leq 10^9 bərabərsizliyi ödənilir.
Axtarılan bitonik altardıcıllıq üçün rəqəmlər cəminin maksimumunu çıxışa yazın. Əgər verilmiş ardıcıllıqda heç bir bitonik altardıcıllıq yoxdursa, çıxışa verin.
Nümunə 1