Dãy số b₁, b₂, . . ., b_m được gọi là hình nón nếu tồn tại j sao cho b₁ < b₂ < . . .< b_j > b_j+1 > . . . > b_m (1 <j<m). Theo định nghĩa ta thấy dãy số hình nón phải có ít nhất 3 phần tử.

Cho dãy số nguyên a₁, a₂, . . ., a_n. Dãy số a_i1, a_i2, . . ., a_ik được gọi là dãy con của dãy đã cho nếu 1 ≤ i₁ < i₂ < . . . < i_k ≤ n.

Yêu cầu:  Cho dãy số nguyên, các số ở hệ thập phân. Hãy xác định dãy con hình nón có tổng các số lớn nhất và đưa ra tổng này.

Dữ liệu: Vào từ file văn bản BITONIC.INP gồm:

• Dòng đầu tiên chứa số nguyên n (3 ≤ n ≤ 1000),
• Dòng thứ 2 chứa n số nguyên a₁, a₂, . . ., a_n (1 ≤ a_i ≤ 10⁵).

Kết quả: Đưa ra file văn bản BITONIC.OUT một số nguyên – kết quả tìm được.

Ví dụ: