Bitonik altardıcıllıq
Bir ardıcıllıq b_1, b_2, ..., b_m bitonik adlanır, əgər elə bir j (1< j < m) ədədi varsa ki, b_1 < b_2 < ... < b_j > b_{j+1} > ... > b_m bərabərsizliyi ödənilir. Bu tərifə görə, bitonik ardıcıllıq ən azı üç elementi ehtiva etməlidir.
Tutaq ki, sizə a_1, a_2, ..., a_n ardıcıllığı verilib. Onun alt ardıcıllığı aşağıdakı formada olan ardıcıllıqdır:
a_i1, a_i2, ..., a_ik
Burada i_1, ..., i_k ədədləri üçün 1 ≤ i_1 ≤ i_2 ≤ ... ≤ i_k ≤ n bərabərsizliyi ödənilməlidir.
Sizin vəzifəniz verilmiş ardıcıllığın bitonik alt ardıcıllığını tapacaq proqram yazmaqdır ki, bu ardıcıllığa daxil olan ədədlərin rəqəmlərinin cəmi maksimum olsun. Burada ədədlərin onluq sistemdə yazıldığı qəbul edilir.
Giriş verilənləri
Giriş faylının ilk sətiri tam n (3 ≤ n ≤ 1000) ədədini ehtiva edir. Giriş faylının ikinci sətiri n tam ədəd a_1, ..., a_n - verilmiş ardıcıllığı ehtiva edir. Onların hər biri üçün 1 ≤ a_i ≤ 10^9 bərabərsizliyi doğrudur.
Çıxış verilənləri
Çıxış faylının ilk sətirində tapılmış bitonik alt ardıcıllığa daxil olan ədədlərin rəqəmlərinin cəmini çıxarın. Əgər verilmiş ardıcıllıqda bitonik alt ardıcıllıq yoxdursa, çıxış faylına -1 ədədini yazın.