P3564.第2题-排列修补
题目内容
游游有一个原始排列，但部分元素丢失，剩余元素形成长度为 n 的数组{a1,a2,…,an}。
对于每个 1≤i≤n ，将前缀 {a1,a2,…,ai} 看作新的数组，要把它补全成一个排列，至少需要插入多少个元素？换句话说，对于每个 1≤i≤n ，考虑由前缀 a1,a2,…,ai 构成的元素集合。要将这个集合补全为一个长度为 m 的排列 (即包含 1,2,…,m )， m 的值必须不小于该集合中的任何元素)。为了使插入的元素数量最少，你需要选择一个最优的 m 。请问在这种最优选择下，至少需要插入多少个元素？
请输出每个前缀所需插入的最少元素数。
【名词解释】
长度为 n 的排列：由 1,2,…,n 这 n 个整数、按任意顺序组成的数组 (每个整数均恰好出现一次)。例如，{ 2,3,1,5,4 }是一个长度为 5 的排列，而 {1,2,2}和{1,3,4}都不是排列，因为前者存在重复元素，后者包含了超出范围的数。
输入描述
第一行输入一个整数 n(1≤n≤2×105)，表示数组的长度；
第二行输入 n 个整数 a1,a2,…,an(1≤ai≤109)，表示数组的元素。
输出描述
一行上输出 n 个整数，用空格分隔。其中第 i 个整数表示前缀 {a1,a2,…,ai}需要插入的最少元素数。
样例1
输入
3
3 1 6
输出
2 1 3
说明
在这个样例中，对于前缀：
-
{3} 最小插入元素数量为 2 ，即插入{1,2};
-
{3,1} 最小插入元素数量为 1，即插入{2};
-
{3,1,6} 最小插入元素数量为 3 ，即插入{2,4,5}。
样例2
输入
5
1 2 3 4 5
输出
0 0 0 0 0
说明
在这个样例中，每个前缀已经是一个排列，无需插入元素。
开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写
