← 返回题目列表

Codeforces · 605/A

A. 分类火车车厢

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

一条无限长的铁路有一辆由 n 节车厢组成的列车,编号从 1 到 n(所有车厢的编号不同),并且按任意顺序排列。大卫·布莱恩想要按照数量递增的顺序对火车车厢进行排序。只需一个动作,他就可以让其中一节车厢从原来的位置消失,并按照他的意愿将其传送到火车的开头或结尾。为了对火车进行排序,大卫·布莱恩需要执行的最少操作次数是多少?

输入

输入的第一行包含整数 n (1 ≤ n ≤ 100 000) — 火车的车厢数量。

第二行包含 n 个整数 pi (1 ≤ pi ≤ n, pi ≠ pj 如果 i ≠ j) — 火车中车厢编号的序列。

输出

打印一个整数 - 对火车车厢进行排序所需的最少操作数。

示例

输入 #1

5
4 1 2 5 3

输出 #1

2

输入 #2

4
4 1 3 2

输出 #2

2

注意

在第一个示例中,您需要首先将第 4 节车厢传送到火车末端,然后将第 5 节车厢传送到火车末端。