// 이상한 토너먼트

#include <iostream>
#include <cstring>
using namespace std;
#include <fstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <vector>
#include <stack>
#include <queue>
#include <functional>
#include <deque>
#include <numeric>
#include <set>
#include <climits>
#include <utility>
#include <map>
#include <algorithm>
#define INF 987654321
typedef long long ll;
typedef unsigned long long ull;
inline int max( int x, int y ){ return x > y ? x : y ; }
inline int min( int x, int y ){ return x < y ? x : y ; }
inline ll max( ll x, ll y ){ return x > y ? x : y ; }
inline ll min( ll x, ll y ){ return x < y ? x : y ; }
inline ull max( ull x, ull y ){ return x > y ? x : y ; }
inline ull min( ull x, ull y ){ return x < y ? x : y ; }


int main(){

	int N, arr[500];
	int dp[500][500];
	int ans[500][500];

	scanf("%d", &N);
	memset( arr, 0, sizeof(arr) );
	memset( dp, 0, sizeof(dp) );
	memset( ans, 0, sizeof(ans) );

	for( int i=0; i<N; ++i ){
		scanf("%d", arr+i );
	}

	for( int i=0; i<N; ++i ){
		for( int j=0; j<N; ++j ){
			if( i > j ) continue;
			if( i == j ){
				dp[i][j] = arr[i];
			}else{
				dp[i][j] = max( dp[i][j-1], arr[j] );
				ans[i][j] = INT_MAX;
			}
		}
	}

	for( int i=N-1; i>=0; --i ){
		for( int j=0; j<N; ++j ){
			for( int k=i; k<j; ++k ){
				if( i>=j ) continue;
				ans[i][j] = min( ans[i][j], ans[i][k]+ans[k+1][j]+abs(dp[i][k]-dp[k+1][j]));
			}
		}
	}

	printf("%d", ans[0][N-1]);
	return 0;
}


// arr[i] : 입력받을 배열
// dp[i][j] : i to j까지 중에서 최댓값을 담을 배열, dp[i][j]는 arr[j]랑 dp[i][j-1]중에 최대값을 구하는 방식으로 갱신.
// dp배열은 그냥 세그먼트트리 구현해서 풀어도 상관 X
// ans[i][j] : i to j까지 경기를 진행했을 때 관중들의 지루함 값의 최소값. 메모이제이션과 재귀로 구현해도 되는데 위는 O(N^3)으로 구현함.
// i to j까지의 최소값을 구하려면 i<=k<j 일때 i to k에서 올라온 선수와 k+1 to j에서 올라온 선수와 경기를 붙어서 나온 결과들을 계속 갱신해야함.