import math





class SegmentTree:

    """

    Segment Tree

    query:

    1. update(i, val): update i-th value to val

    2. query(low, high): find f(value) in [low, high)

    time complexity: O(log n)

    space complexity: O(2n)

    """

    def __init__(self, N, f, default):

        self.N = 1 << math.ceil(math.log(N, 2))

        self.default = default

        self.f = f

        self.segtree = [self.default] * (self.N * 2 - 1)



    def update(self, i, val):

        i += self.N - 1

        self.segtree[i] = val

        while i > 0:

            i = (i - 1) // 2

            self.segtree[i] = self.f(self.segtree[2*i+1], self.segtree[2*i+2])



    def query(self, low, high, k=0, left=0, right=-1):

        if right == -1:

            right = self.N

        if right <= low or high <= left:

            return self.default



        if low <= left and right <= high:

            return self.segtree[k]

        else:

            mid = (left + right) // 2

            return self.f(self.query(low, high, 2*k+1, left, mid),

                          self.query(low, high, 2*k+2, mid, right))





N = int(eval(input()))

X = [int(x) for x in input().split()]

dp = SegmentTree(N, lambda x, y: max(x, y), 0)

for x, i in sorted((x, i) for i, x in enumerate(X)):

    dp.update(i, dp.query(0, i) + x)

print((N * (N + 1) // 2 - dp.query(0, N)))
import math





class FenwickTree:

    def __init__(self, a_list, f, default):

        # 0-indexed

        self.N = len(a_list)

        self.bit = a_list[:]

        self.f = f

        self.default = default

        for _ in range(self.N, 1 << (math.ceil(math.log(self.N, 2)))):

            self.bit.append(self.default)

        for i in range(self.N - 1):

            self.bit[i | (i + 1)] = self.f(self.bit[i | (i + 1)], self.bit[i])



    def update(self, i, val):

        while i < self.N:

            self.bit[i] = self.f(self.bit[i], val)

            i |= i + 1



    def query(self, n):

        # [0, n]

        ret = 0

        while n >= 0:

            ret = self.f(ret, self.bit[n])

            n = (n & (n + 1)) - 1

        return ret





N = int(eval(input()))

X = [int(x) for x in input().split()]

dp = FenwickTree([0] * N, lambda x, y: max(x, y), 0)

for x, i in sorted((x, i) for i, x in enumerate(X)):

    dp.update(i, dp.query(i) + x)

print((N * (N + 1) // 2 - dp.query(N - 1)))
import math


class SegmentTree:
    """
    Segment Tree
    query:
    1. update(i, val): update i-th value to val
    2. query(low, high): find f(value) in [low, high)
    time complexity: O(log n)
    space complexity: O(2n)
    """

    def __init__(self, N, f, default):
        self.N = 1 << math.ceil(math.log(N, 2))
        self.default = default
        self.f = f
        self.segtree = [self.default] * (self.N * 2 - 1)

    def update(self, i, val):
        i += self.N - 1
        self.segtree[i] = val
        while i > 0:
            i = (i - 1) // 2
            self.segtree[i] = self.f(self.segtree[2 * i + 1], self.segtree[2 * i + 2])

    def query(self, low, high, k=0, left=0, right=-1):
        if right == -1:
            right = self.N
        if right <= low or high <= left:
            return self.default
        if low <= left and right <= high:
            return self.segtree[k]
        else:
            mid = (left + right) // 2
            return self.f(
                self.query(low, high, 2 * k + 1, left, mid),
                self.query(low, high, 2 * k + 2, mid, right),
            )


N = int(eval(input()))
X = [int(x) for x in input().split()]
dp = SegmentTree(N, lambda x, y: max(x, y), 0)
for x, i in sorted((x, i) for i, x in enumerate(X)):
    dp.update(i, dp.query(0, i) + x)
print((N * (N + 1) // 2 - dp.query(0, N)))

import math


class FenwickTree:
    def __init__(self, a_list, f, default):
        # 0-indexed
        self.N = len(a_list)
        self.bit = a_list[:]
        self.f = f
        self.default = default
        for _ in range(self.N, 1 << (math.ceil(math.log(self.N, 2)))):
            self.bit.append(self.default)
        for i in range(self.N - 1):
            self.bit[i | (i + 1)] = self.f(self.bit[i | (i + 1)], self.bit[i])

    def update(self, i, val):
        while i < self.N:
            self.bit[i] = self.f(self.bit[i], val)
            i |= i + 1

    def query(self, n):
        # [0, n]
        ret = 0
        while n >= 0:
            ret = self.f(ret, self.bit[n])
            n = (n & (n + 1)) - 1
        return ret


N = int(eval(input()))
X = [int(x) for x in input().split()]
dp = FenwickTree([0] * N, lambda x, y: max(x, y), 0)
for x, i in sorted((x, i) for i, x in enumerate(X)):
    dp.update(i, dp.query(i) + x)
print((N * (N + 1) // 2 - dp.query(N - 1)))

-class SegmentTree: -    """ -    Segment Tree -    query: -    1. update(i, val): update i-th value to val -    2. query(low, high): find f(value) in [low, high) -    time complexity: O(log n) -    space complexity: O(2n) -    """ - -    def __init__(self, N, f, default): -        self.N = 1 << math.ceil(math.log(N, 2)) +class FenwickTree: +    def __init__(self, a_list, f, default): +        # 0-indexed +        self.N = len(a_list) +        self.bit = a_list[:] +        self.f = f -        self.f = f -        self.segtree = [self.default] * (self.N * 2 - 1) +        for _ in range(self.N, 1 << (math.ceil(math.log(self.N, 2)))): +            self.bit.append(self.default) +        for i in range(self.N - 1): +            self.bit[i | (i + 1)] = self.f(self.bit[i | (i + 1)], self.bit[i]) -        i += self.N - 1 -        self.segtree[i] = val -        while i > 0: -            i = (i - 1) // 2 -            self.segtree[i] = self.f(self.segtree[2 * i + 1], self.segtree[2 * i + 2]) +        while i < self.N: +            self.bit[i] = self.f(self.bit[i], val) +            i |= i + 1 -    def query(self, low, high, k=0, left=0, right=-1): -        if right == -1: -            right = self.N -        if right <= low or high <= left: -            return self.default -        if low <= left and right <= high: -            return self.segtree[k] -        else: -            mid = (left + right) // 2 -            return self.f( -                self.query(low, high, 2 * k + 1, left, mid), -                self.query(low, high, 2 * k + 2, mid, right), -            ) +    def query(self, n): +        # [0, n] +        ret = 0 +        while n >= 0: +            ret = self.f(ret, self.bit[n]) +            n = (n & (n + 1)) - 1 +        return ret -dp = SegmentTree(N, lambda x, y: max(x, y), 0) +dp = FenwickTree([0] * N, lambda x, y: max(x, y), 0) -    dp.update(i, dp.query(0, i) + x) -print((N * (N + 1) // 2 - dp.query(0, N))) +    dp.update(i, dp.query(i) + x) +print((N * (N + 1) // 2 - dp.query(N - 1)))