问题 1181. -- 书的排序

1181: 书的排序

时间限制: 1 Sec  内存限制: 128 MB
提交: 52  解决: 14
[提交][状态][讨论版]

题目描述

 

Mirko1个家庭图书馆,一共有N本书,从下往上叠放成一堆。Mirko可以很轻松的从书堆里抽出1本书,但是他要把它放进去就麻烦了,当然如果放在书堆顶部很简单。于是,Mirko总是从书堆里抽出1本书,并把它放在书堆的顶部,这是唯一有效的操作。Mirko不会再做其他的操作。

这些书按字典序从1N已经编号了号。接下来,Mirko想要把他们按照从上到下是编号从1N递增的顺序来重新排列。比如,现在有三本书,从上到下分别为3,2,1.Mirko只需要2次操作就可以让书排好序。他先将2抽出放到最上面,再将1抽出放到最上面。

你来帮Mirko计算他要完成排序任务的最少的操作次数。

输入

 1行包含一个整数NN<=300000接下来N行,每一行包含1个正整数。这N个正整数表示开始时,书堆中从上到下书的编号,每个整数只出现1次。

输出

1行,表示Mirko最少需要移动的次数。

样例输入

3 
3 
2 
1

样例输出

2

提示

来源

[提交][状态]