UOJ Logo LFYZ Online Judge

LFYZOJ

#14. 放置书本

统计

问题描述

在生活中,我们经常见到这样的情形:

示意图

有一摞书放在地上,而且它们的编号是乱的。你想把它们的编号搞成从上往下依次是递增的。

为了达成你的目的,你被允许每次从书堆里拿出一本书,并将其放到书堆的最上边。

输出为了达成你的目的的最少操作次数。

输入格式

第一行是一个数 $n$,代表有多少本书。

第二行是 $n$ 个数,代表从上往下书的编号。

输出格式

输出一个数,是你把它们的编号搞成从上往下依次是递增的所需要的最少操作次数。

样例一

input

4
4 1 2 3

output

3

explanation

你先拿出3,放到顶上,变成了3 4 1 2

你再拿出2,放到顶上,变成了2 3 4 1

你最后拿出1,放到顶上,变成了1 2 3 4。你达到了你的目的,并且知道了答案是3。

数据范围与约定

对于$10\%$的数据,$n\leq 2$。

对于$30\%$的数据,$n\leq 15$。

对于$60\%$的数据,$n\leq 2000$。

对于$100\%$的数据,$n\leq 100000$,第二行输入数据保证是从1到 $n$ 的一个排列。

时间限制: $1\mathrm{s}$

内存限制: $256\mathrm{MB}$

下载

样例数据下载

来源

origin HDU 5500