题目描述

给定一个排列 $A$，你每次可以进行如下操作：

• 选择一个数 $x$，并把它放到序列的最前面。

求最少进行多少次使得序列为从小到大排序。

输入格式

第一行一个整数 $n$，表示序列长度。

第二行 $n$ 个整数，表示排列 $A$。保证 $1\le a_i\le n$ 且所有数互不相同。

输出格式

输出一个整数，表示最小的次数。

5
4 5 2 1 3

3

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

21

数据范围

对于所有数据，$1\le n\le 2\times10^5$，且 $A$ 为排列。