分数: 500 点
问题陈述
给你一个序列 (P_1,P_2,...,P_N) 这是来自以下整数的排列 1 通过 N。 您想通过重复以下操作来按升序对该序列进行排序:
- 选择序列中的一个元素并将其移动到序列的开头或结尾。
找出所需的最少操作数。 可以证明,使用这个操作确实可以对序列进行排序。
约束
- 1 \leq N \leq 2\times 10^5
- (P_1,P_2,...,P_N) 是一个排列 (1,2,...,N).
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N P_1 : P_N
输出
打印所需的最少操作数。
示例输入 1
4 1 3 2 4
示例输出 1
2
例如,序列可以按升序排序,如下所示:
- 移动 2 到开头。现在的顺序是 (2,1,3,4).
- 移动 1 到开头。现在的顺序是 (1,2,3,4).
示例输入 2
6 3 2 5 1 4 6
示例输出 2
4
示例输入 3
8 6 3 1 2 7 4 8 5
示例输出 3
5