# Appreciation

/*
 * Problem :: 7570 / 줄 세우기
 *
 * Kind :: Dynamic Programming
 *
 * Insight
 * - 5 2 4 1 3
 *   어린이들이 위와같은 순서로 줄을 서있다고 하자
 *   1,4,5번 어린이를 움직여서
 *   1 2 3 4 5
 *   로 줄을 세울 수 있다
 *   이때 2,3번 어린이는 움직이지 않았다
 *   + 1번 어린이가 움직이지 않게 할 수 있을까?
 *     2,3,4,5번 어린이를 맨 뒤로 보내면 된다
 *   + 3번 어린이가 움직이지 않게 할 수 있을까?
 *     1,2번 어린이를 맨 앞에, 4,5번 어린이를 맨 뒤로 보내면 된다
 *   + 2,4번 어린이가 움직이지 않게 할 수 있을가?
 *     2번 어린이 뒤에는 3번 어린이가 와야하고
 *     4번 어린이 앞에는 3번 어린이가 와야하기 때문에
 *     적어도 두 어린이 중 한 어린이는 이동해야 한다
 *     # 움직이지 않는 어린이들을 선택하려면
 *       주어진 번호들 사이에서 공차가 1인 등차수열을 이루는 번호들을 선택해야 한다!!!
 *       최소로 움직이려면 움직이지 않는 어린이들을 최대한 많이 선택해야 하고
 *       이는 주어진 번호들 사이에서 가장 긴 공차 1의 등차수열의 길이를 찾는 것이다!!!
 *
 * - 그걸 어케 찾지?
 *   + 주어진 번호들이 배열 A 에 저장되어있다고 할 때
 *     A[i] = 3 이라면
 *     dp[j] = j 로 끝나는 가장 긴 공차 1의 등차수열의 길이
 *     라는 정보가 있어서
 *     dp[3] = dp[2] + 1
 *     로 구해야 되는데...
 *     # 그러면 그렇게 구하면 되지 뭐
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <cstring>

using namespace std;

#define endl '\n'

// Set up : Global Variables
/* None */

// Set up : Functions Declaration
/* None */


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    int N; cin >> N;
    int A[N];
    for (int i=0; i<N; i++)
        cin >> A[i];

    // Process
    int dp[N+1]; /* dp[j] = j 로 끝나는 가장 긴 공차 1의 등차수열의 길이 */
    memset(dp, 0, sizeof(dp)); /* dp 초기화 <= 처음에는 모두 0 의 값을 가짐 */

    int mx = -1; /* 움직이지 않아도 되는 어린이들 수의 최댓값
                  * 가장 긴 공차 1의 등차수열의 길이 */
    for (int i=0; i<N; i++) {
        /* A[i] 로 끝나는 가장 긴 공차 1의 등차수열의 길이는
         * A[i]-1 로 끝나는 가장 긴 공차 1의 등차수열의 길이 + 1 로 구할 수 있음 */
        dp[A[i]] = dp[A[i]-1] + 1;
        /* 나중에 최댓값 따로 찾기 귀찮으니 <= *max_element 쓰면 되는데???
         * 방금 구한 dp[A[i]] 의 값을 비교하여 최댓값 갱신 */
        mx = max(mx, dp[A[i]]);
    }

    // Control : Output
    /* 움직여야 하는 어린이들의 최솟값
     *     = 전체 어린이들 수 - 움직이지 않아도 되는 어린이들 수의 최댓값 */
    cout << N-mx << endl;
}

// Helper Functions
/* None */