#514. 整理代码模板

整理代码模板

题目背景

桃桃扫描了一份大神的代码模板,却发现电子文档中的页面顺序被打乱了。他想通过编辑器,将页面恢复为原来的顺序。

题目描述

文档共有 nn 页,按当前从前到后的顺序,页面上印着的原始页码为 a1,a2,…,ana_1,a_2,\ldots,a_n,它们是 11 到 nn 的一个排列*。

每次操作,桃桃可以选中任意一页,将其从原位置取出,再插入剩余页面的最前面或最后面。取出并插入合计为一次操作,其他页面的相对顺序保持不变。同一页可以被多次移动,页面上的原始页码始终不变。

求使文档中的原始页码从前到后依次为 1,2,…,n1,2,\ldots,n 所需的最少操作次数。

*:长度为 nn 的排列是一个包含 nn 个数的序列,其中 11 到 nn 的每个整数恰好出现一次。例如,[2,3,1][2,3,1] 是长度为 33 的排列,而 [1,1,3][1,1,3] 不是。

输入格式

第一行包含一个整数 nn,表示文档的页数。

第二行包含 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n,表示文档中各页面从前到后的原始页码。

输出格式

输出一个整数,表示最少操作次数。

样例

样例输入 1

5
5 1 2 3 4

样例输出 1

1

样例输入 2

5
5 2 3 1 4

样例输出 2

2

样例说明

对于样例 11,将原始页码为 55 的页面移至文档末尾,页码顺序即变为 1,2,3,4,51,2,3,4,5,最少需要 11 次操作。

对于样例 22,一种最优操作方案如下:

  1. 将原始页码为 11 的页面移至文档开头,页码顺序变为 1,5,2,3,41,5,2,3,4。
  2. 将原始页码为 55 的页面移至文档末尾,页码顺序变为 1,2,3,4,51,2,3,4,5。

无法通过一次操作完成排序,因此最少需要 22 次操作。

数据范围

对于所有测试数据:

  • 1≤n≤2×1051\le n\le 2\times 10^5;
  • 保证输入序列是 11 到 nn 的一个排列。

时间限制: 2s2\text{s}。
空间限制: 256MB256\text{MB}。