← 返回题目列表

AtCoder · agc024_b

B. 背面

中文机器翻译题面 查看原题

分数: 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