만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

조교는 새디스트야!!

면접 대비

시간 제한2초메모리 제한256 MB

요약
1부터 N까지의 순열이 주어질 때, 남은 수가 앞에서 뒤로 증가하도록 제거해야 하는 최소 원소 수를 구한다.
난이도

보통10점 중 4점

유형
동적 계획법, 이분 탐색, 배열, 정렬
정답자
아직 제출이 없습니다

문제

헌우네 반이 제주도로 수학여행을 갔다. 공항을 나서자 선글라스를 쓴 조교가 기다리고 있었다.

"번호 순서대로 서지 않은 사람은 전부 맞을 각오하십시오."

조교는 줄에 서 있는 학생 중 몇 명을 골라 때린다. 맞은 학생이 줄에서 빠지고 나면, 남은 학생의 번호는 앞에서 뒤로 가면서 계속 커져야 한다. 조교는 때리는 인원을 최소로 한다.

학생 수 NN과 학생들의 번호가 지금 줄 서 있는 순서대로 주어질 때, 맞는 학생이 몇 명인지 구하여라.

입력

첫째 줄에 헌우네 반 학생 수 NN이 주어진다. (1≤N≤200001 \le N \le 20000)

둘째 줄에 학생 NN명의 번호가 지금 줄 서 있는 순서대로 공백으로 구분되어 주어진다. 번호는 11 이상 NN 이하이고, 중복되는 번호는 없다.

출력

첫째 줄에 맞는 학생 수를 출력한다.

예제4

  1. 예제 1

    입력
    5
    3 2 5 4 1
    
    예상 출력
    3
    
  2. 예제 2

    입력
    1
    1
    
    예상 출력
    0
    
  3. 예제 3

    입력
    8
    1 2 3 4 5 6 7 8
    
    예상 출력
    0
    
  4. 예제 4

    입력
    8
    8 7 6 5 4 3 2 1
    
    예상 출력
    7