TouchStone
  请登录后使用
登录 注册
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P7823
  • 题目
  • P7823家庭图书馆
    限制 : 时间限制 : - MS   空间限制 : - KB
    评测说明 : 1s 256MB
    问题描述

    果老师有一个由 \(n\) 本书组成的家庭图书馆,\(n\) 本书在一个狭窄的橱柜中一个接一个地排列。由于在上一任务中对字母进行了很好的训练,他现在希望按字母顺序排列书籍,以使书名字典序排第一的书排在最后,而字典序排最后的书在书橱的底部。

    果老师可以轻松地将书从书橱中拉出,但是很难将其推回书橱中,因此只能将书放回到书橱的顶部。因此,将书排序籍的唯一可用方法是反复将书籍从书橱中拉出并将其放在书橱的顶部。

    这些书按字母顺序用从 $1$ 到 \(n\) 的整数标记。因此,果老师 希望从顶部开始将它们排序为 \((1,2, \cdots ,n)\)。例如,如果 \(n = 3\) 且开始顺序为 \((3,2,1)\),则两步就足够了。首先,他拉出编号为 $2$ 的书并将其放在最上面,这样书的顺序便变成 \((2,3,1)\)。之后,他对编号为 $1$ 的书执行相同操作,因此书的顺序变成 \((1,2,3)\)

    计算给定起始顺序,排序完毕所需的最少移动次数。

    输入格式

    第一行一个整数 \(n\),具体含义请见题目描述。

    接下来 \(n\) 行,每行一个正整数,表示书籍的初始摆放顺序。

    保证 $1 \leq n \leq 3 \times 10^5$,书籍的初始摆放顺序为 $1\ldots n$ 的一个排列

    输出格式

    一行一个整数,表示使书籍按照自然数顺序排列所需的最小移动步数。

    样例输入 1

    3
    3
    2
    1

    样例输出 1

    2

    样例输入 2

    4
    1
    3
    4
    2

    样例输出 2

    2