最大合計を持つ最長増加部分列

n 個の整数からなる配列が与えられたとき、この配列の最長増加部分列を求めます。複数該当する部分列がある場合は、そのうちどれを出力しても構いません。

配列の部分列とは、残った要素の順序を変えずにいくつか（0 個でも可）の要素を削除することで得られるものです。例えば、配列が の場合、 は の部分列です。しかし、 は要素の順序が変わっているため、 の部分列にはなりません。

入力

入力の最初の行には、配列の長さを示す整数 n (1 ≤ n ≤ 1000) が与えられます。

続く 2 行目には、配列の要素となる n 個の整数 () がスペース区切りで与えられます。

出力

最大合計を持つ最長増加部分列の合計を出力してください。

解説

1. 最初の例では、合計値が最大となる最長増加部分列は です。

2. 2 番目の例では、合計値が最大となる最長増加部分列は です。