#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
using ull = uint64_t;
const int N = 5007;
const ull INF = numeric_limits<ull>::max();
int n;
int h[N];
ull d[N][N];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> h[i];
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n - 1; ++j) {
d[i][j] = INF;
}
}
priority_queue<pair<ull, pair<int, int>>, vector<pair<ull, pair<int, int>>>, greater<pair<ull, pair<int, int>>>> q;
auto upd = [&](int i, int j, ll dd) {
if (dd < d[i][j]) {
d[i][j] = dd;
q.push({dd, {i, j}});
}
};
upd(0, n - 2, 0);
while (!q.empty()) {
auto z = q.top();
q.pop();
auto [i, j] = z.second;
if (d[i][j] != z.first) {
continue;
}
if (i == j || i - 1 == j) {
cout << d[i][j] << endl;
return 0;
}
if (h[i] == h[j]) {
if (j > 0) {
upd(i, j - 1, d[i][j]);
}
upd(j, i, d[i][j]);
}
if (h[i] == h[j + 1]) {
if (j < n - 1) {
upd(i, j + 1, d[i][j]);
}
upd(j + 1, i, d[i][j]);
}
for (int ii : {i - 1, i + 1}) {
if (ii < 0 || n <= ii) {
continue;
}
if (h[i] < h[ii]) {
if (h[i] < h[j]) {
if (h[ii] - h[i] <= h[j] - h[i]) {
upd(ii, j, d[i][j] + h[ii] - h[i]);
} else {
upd(j, min(ii, i), d[i][j] + h[j] - h[i]);
}
} else {
if (h[ii] - h[i] <= h[j + 1] - h[i]) {
upd(ii, j, d[i][j] + h[ii] - h[i]);
} else {
upd(j + 1, min(ii, i), d[i][j] + h[j + 1] - h[i]);
}
}
}
if (h[i] > h[ii]) {
if (h[i] > h[j]) {
if (-h[ii] + h[i] <= -h[j] + h[i]) {
upd(ii, j, d[i][j] - h[ii] + h[i]);
} else {
upd(j, min(ii, i), d[i][j] - h[j] + h[i]);
}
} else {
if (-h[ii] + h[i] <= -h[j + 1] + h[i]) {
upd(ii, j, d[i][j] - h[ii] + h[i]);
} else {
upd(j + 1, min(ii, i), d[i][j] - h[j + 1] + h[i]);
}
}
}
}
}
cout << "NO" << endl;
return 0;
}
