#include #include #include #include #include using namespace std; using ll = long long; template using grid = vector>; #define REP(i,n) for(ll i=0;i<(ll)(n);i++) #define REPD(i,n) for(ll i=n-1;i>=0;i--) #define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++) #define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--) #define input(...) __VA_ARGS__; in(__VA_ARGS__) void print() { std::cout << std::endl; } template void print(Head&& head, Tail&&... tail) { std::cout << head << " "; print(std::forward(tail)...); } void in() { } template void in(Head&& head, Tail&&... tail) { cin >> head; in(std::forward(tail)...); } int main() { ll input(n); vector y(n); REP(i, n) cin >> y[i]; ll YMAX = 10000; vector> table(n + 1); REP(i, n + 1) { if (i == n) table[i] = vector(YMAX + 1, 0); else table[i] = vector(YMAX + 1); } REPD(i, n) { vector tmp(YMAX + 1); ll minv = LLONG_MAX; FORD(j, YMAX, 0) { minv = min(minv, table[i + 1][j] + abs(y[i] - j)); tmp[j] = minv; } FORD(h, YMAX, 0) { table[i][h] = tmp[h]; } } print(table[0][0]); }