Sorting Railway Cars

题意翻译

## 题意 给出一个 1 到 n 的排列，每次操作可以将某个位置的数字移动到最前面或最后面，求将排列从小到大排序的最小操作次数 #### 如：4 1 2 5 3 操作1：将5和3换一下变成4 1 2 3 5 #### 操作2：将1 2 3和 4换一下变成 1 2 3 4 5 在此后即完成要求。所以最小操作次数为2。 ## 输入： 第一行 为长度$n$; 第二行为原来的顺序两个数之间有空格。 ## 输出： 最小操作次数 ## 范围 $ 1<=n<=100000 $ $ 1=<p[i]<=n $ $ p[i]!=p[j] 当 i!=j $ 感谢@__CDy @ydnhaha 提供的翻译

题目描述

An infinitely long railway has a train consisting of $ n $ cars, numbered from $ 1 $ to $ n $ (the numbers of all the cars are distinct) and positioned in arbitrary order. David Blaine wants to sort the railway cars in the order of increasing numbers. In one move he can make one of the cars disappear from its place and teleport it either to the beginning of the train, or to the end of the train, at his desire. What is the minimum number of actions David Blaine needs to perform in order to sort the train?

输入输出格式

输入格式

The first line of the input contains integer $ n $ ( $ 1<=n<=100000 $ ) — the number of cars in the train. The second line contains $ n $ integers $ p_{i} $ ( $ 1<=p_{i}<=n $ , $ p_{i}≠p_{j} $ if $ i≠j $ ) — the sequence of the numbers of the cars in the train.

输出格式

Print a single integer — the minimum number of actions needed to sort the railway cars.

输入输出样例

输入样例 #1

5
4 1 2 5 3

输出样例 #1

2

输入样例 #2

4
4 1 3 2

输出样例 #2

2

说明

In the first sample you need first to teleport the $ 4 $ -th car, and then the $ 5 $ -th car to the end of the train.