TouchStone
  Please Login
Login Sign Up
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P5748
  • Problem
  • P5748站队
    Limits : Time Limit : - MS   Memory Limit : - KB
    Judgment Tips : 1s,256m
    Description

    一年一度的NK自编操比赛即将到来。
    今年学校要求每个班级和社团都要参加,信竞队也不例外。于是何老板组织队员们到操场排练。
    信竞队有n名队员,学号编号1到n。
    何老板要求大家按学号由小到大站成一队。但是自由散漫的同学们站了成乱序的一队,这让何老板很是恼火,于是他得将大家调整成有序的一队。
    何老板决定按下列操作调整:
       选一个同学,将他移动到队首或队尾。
    何老板想知道,他最少需要操作几次就能将队伍调整成学号由小到大的顺序。

    Input Format

    第一行,一个整数n
    接下来n行,每行一个整数,第i行表示左起第i个同学的学号

    Output Format

    一个整数,表示最少所需的操作次数。
    题目保证一定有解。

    Sample Input 1

    4
    1
    3
    2
    4

    Sample Output 1

    2

    样例解释:
    将2移动到队首,得到2,1,3,4  
    将1移动到对首,得到1,2,3,4

    Sample Input 2

    6
    3
    2
    5
    1
    4
    6

    Sample Output 2

    4

    Sample Input 3

    8
    6
    3
    1
    2
    7
    4
    8
    5

    Sample Output 3

    5

    Hint

    $1≤n≤2*10^5$


    Source  AGC024B - Backfront