import std.algorithm;
import std.array;
import std.conv;
import std.math;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

int readint() {
    return readln.chomp.to!int;
}

int[] readints() {
    return readln.split.map!(to!int).array;
}

void main() {
    readln;
    auto xs = readints();

    int n = cast(int) xs.length;
    auto segTree = new SegmentTree(n + 1);
    foreach (x; xs) {
        auto max = segTree.query(1, x);
        segTree.update(x, x + max);
    }

    auto max = segTree.query(1, n + 1);
    writeln(cast(long) n * (n + 1) / 2 - max);
}

class SegmentTree {
    private long[] _data;

    this(int n) {
        int len = 1;
        while (len < n)
            len *= 2;

        _data = new long[len * 2];
    }

    /// k ?????????????´????(0-indexed)??? a ????????´
    void update(int k, long a) {
        // ????????\???
        k += (_data.length / 2) - 1;
        _data[k] = a;
        // ?????????????????´??°
        while (k > 0) {
            k = (k - 1) / 2;
            _data[k] = max(_data[k * 2 + 1], _data[k * 2 + 2]);
        }
    }

    /// [a, b) ???????°????????±???????
    long query(int a, int b, int k, int l, int r) {
        // [a, b) ??¨ [l, r) ??????????????????
        if (r <= a || b <= l)
            return 0;

        // [a, b) ??? [l, r) ????????¨???????????§????????°???????????\?????????
        if (a <= l && r <= b) {
            return _data[k];
        }

        // ????????§???????????°???2 ?????????????????§???
        auto vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
        auto vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
        return max(vl, vr);
    }

    long query(int a, int b) {
        return query(a, b, 0, 0, cast(int)(_data.length / 2));
    }
}