一条无限长的铁路有一辆由 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 节车厢传送到火车末端。