#include <stdio.h>
#include <stdlib.h>

int n;
int *hradby;
int *stit;

int max(int a, int b) {
	return a > b ? a : b;
}

int vyska(int k, int pozice) { // Výška hradby po k útocích
	return max(hradby[pozice]-k, 0);
}

int main(int argc, char *argv[]) {
	scanf("%d", &n); // Počet úseků hradeb
	hradby = malloc(sizeof(int)*n);
	stit = malloc(sizeof(int)*n);

	int i; // Čtení výšek jednotlivých úseků hradeb
	for (i = 0; i < n; i++) {
		scanf("%d", &hradby[i]);
		stit[i] = hradby[i]; // Začínáme nultým krokem
	}

	int k;
	for (k = 1; k < n; k++) { // nejvýše n kroků rozšiřování
		for (i = 0; i < n-k; i++) { // nechť a=i, b=a+k
			// předchozí stit[i] = Š(a,b-1)
			// nový stit[i] = Š(a,b)
			stit[i] = max(
				stit[i]+vyska(k,i+k),
				stit[i+1]+vyska(k,i));
			// Š(a,b) = max{ Š(a,b-1)+V(k,b) , Š(a+1,b)+V(k,a) }
		}
	}

	printf("Nejlepsi soucet ochranenych vysek je %d\n", stit[0]); // Š(0,N-1)

	free(hradby);
	free(stit);

	return 0;
}