Subsecuencia creciente más larga con suma máxima

Dado un arreglo de n enteros, se te pide encontrar la subsecuencia creciente más larga de dicho arreglo. Si existen varias subsecuencias con esta misma longitud, puedes imprimir cualquiera de ellas.

Una subsecuencia de un arreglo se obtiene eliminando algunos (posiblemente cero) elementos del arreglo, sin alterar el orden de los que quedan. Por ejemplo, si el arreglo es , entonces es una subsecuencia de , pero no lo es, puesto que no se preserva el orden original de los elementos.

Entrada

La primera línea de la entrada contiene un único entero n (1 ≤ n ≤ 1000), que representa la longitud del arreglo.

La segunda línea contiene n enteros separados por espacio (), que son los elementos del arreglo.

Salida

El programa debe imprimir la suma de la subsecuencia creciente más larga que tenga la suma máxima.

Explicación

1. En el primer ejemplo, la subsecuencia creciente más larga con suma máxima es .

2. En el segundo ejemplo, la subsecuencia creciente más larga con suma máxima es .