Аналитик изучает последовательность из n числовых показателей, записанных по порядку наблюдения.

Он хочет выбрать несколько показателей так, чтобы:

• выбранные элементы образовывали подпоследовательность исходной последовательности;
• значения в выбранной подпоследовательности были строго возрастающими;
• сумма выбранных значений была как можно больше.

Требуется определить максимальную возможную сумму такой строго возрастающей подпоследовательности.

Входные данные

Первая строка содержит целое число n — количество показателей.

Вторая строка содержит n целых чисел a_i — значения показателей в порядке наблюдения.

Выходные данные

Выведите одно целое число — максимальную сумму строго возрастающей подпоследовательности.

Ответ может не помещаться в 32-битный целочисленный тип.

Ограничения

• 1 <= n <= 5000
• -10^9 <= a_i <= 10^9

Примеры

Пример 1

Входные данные

5
1 101 2 3 100

Выходные данные

106

Пояснение

Подпоследовательность 1, 2, 3, 100 даёт сумму 106.

Пример 2

Входные данные

1
0

Выходные данные

0

Пример 3

Входные данные

2
-3 4

Выходные данные

4