#514. 整理代码模板
整理代码模板
题目背景
桃桃扫描了一份大神的代码模板,却发现电子文档中的页面顺序被打乱了。他想通过编辑器,将页面恢复为原来的顺序。
题目描述
文档共有 页,按当前从前到后的顺序,页面上印着的原始页码为 ,它们是 到 的一个排列*。
每次操作,桃桃可以选中任意一页,将其从原位置取出,再插入剩余页面的最前面或最后面。取出并插入合计为一次操作,其他页面的相对顺序保持不变。同一页可以被多次移动,页面上的原始页码始终不变。
求使文档中的原始页码从前到后依次为 所需的最少操作次数。
*:长度为 的排列是一个包含 个数的序列,其中 到 的每个整数恰好出现一次。例如, 是长度为 的排列,而 不是。
输入格式
第一行包含一个整数 ,表示文档的页数。
第二行包含 个整数 ,表示文档中各页面从前到后的原始页码。
输出格式
输出一个整数,表示最少操作次数。
样例
样例输入 1
5
5 1 2 3 4
样例输出 1
1
样例输入 2
5
5 2 3 1 4
样例输出 2
2
样例说明
对于样例 ,将原始页码为 的页面移至文档末尾,页码顺序即变为 ,最少需要 次操作。
对于样例 ,一种最优操作方案如下:
- 将原始页码为 的页面移至文档开头,页码顺序变为 。
- 将原始页码为 的页面移至文档末尾,页码顺序变为 。
无法通过一次操作完成排序,因此最少需要 次操作。
数据范围
对于所有测试数据:
- ;
- 保证输入序列是 到 的一个排列。
时间限制: 。
空间限制: 。