题目描述

Duang 勤工俭学做上了纪雅的图书管理员，学校让他管理一个小图书室，里面有 $n$ 本书，放书的地方是一个非常狭窄的书柜，以至于只能把一本书放在另一本书的上面，现在 Duang 要做的工作是把书按照编号排序。

Duang 能轻易地把一本书从书柜里拔出来，但放到一堆书中去非常困难，所以只能把拔出来的书放到最上面，故排序的唯一方法就是不停地拔出一本书再放到最上方。

给定 $n$ 本书从上到下的编号 $a_i$，每本书的编号各不相同，要求 Duang 通过一些移动（可以不移动）使得书柜中的书从上到下依次为 $1,2,\cdots,n$，求出最少的移动次数。例如当 $n=3$ 时，一开始的编号为 $\{3,2,1\}$，两次移动就可以完成：第一次拔出 $2$ 放到最上面变为 $\{2,3,1\}$，第二次拔出 $1$ 放到最上面变为 $\{1,2,3\}$。

输入格式

两行，第一行一个正整数 $n$，表示书的数量。第二行 $n$ 个正整数 $a_i$，表示第 $i$ 本书的编号。

输出格式

一行一个自然数，表示最少的移动次数。

3
3 2 1

2

20
1 17 14 2 20 3 11 4 19 5 6 12 8 7 18 16 9 13 10 15

13

数据范围限制

对于 $100\%$ 的数据，$1\le n\le 2\times 10^5,1\le a_i\le n$，保证 $a_i$ 为一个排列。