TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P5748
  • 题目
  • P5748站队
    限制 : 时间限制 : - MS   空间限制 : - KB
    评测说明 : 1s,256m
    问题描述

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

    输入格式

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

    输出格式

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

    样例输入 1

    4
    1
    3
    2
    4

    样例输出 1

    2

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

    样例输入 2

    6
    3
    2
    5
    1
    4
    6

    样例输出 2

    4

    样例输入 3

    8
    6
    3
    1
    2
    7
    4
    8
    5

    样例输出 3

    5

    提示

    $1≤n≤2*10^5$


    来源  AGC024B - Backfront