思路

• 关键结论：对前缀 $a_1,\dots,a_i$ 的元素集合 $S_i$，令

  • $M_i=\max(S_i)$
  • $D_i=|S_i|$（不同元素个数）

• 因为 $m$ 必须满足 $m\ge M_i$，且集合中所有元素都不超过 $m$，所以在任意 $m\ge M_i$ 下，已有的属于 $1..m$ 的不同元素个数就是 $D_i$。要补全为 $1..m$ 的排列，需要插入的数量为 $m-D_i$。当取最小可行的 $m=M_i$ 时插入数最少。

• 因而答案为：

题目内容

游游有一个原始排列，但部分元素丢失，剩余元素形成长度为 $n$ 的数组{$a_1,a_2,…,a_n$}。

对于每个 $1≤i≤n$ ，将前缀 {$a_1,a_2,…,a_i$} 看作新的数组，要把它补全成一个排列，至少需要插入多少个元素？换句话说，对于每个 $1≤i≤n$ ，考虑由前缀 $a_1,a_2,…,a_i$ 构成的元素集合。要将这个集合补全为一个长度为 $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×10^5)$，表示数组的长度；

第二行输入 $n$ 个整数 $a_1,a_2,…,a_n(1≤a_i≤10^9)$，表示数组的元素。

输出描述

一行上输出 $n$ 个整数，用空格分隔。其中第 $i$ 个整数表示前缀 {$a_1,a_2,…,a_i$}需要插入的最少元素数。

样例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

说明

在这个样例中，每个前缀已经是一个排列，无需插入元素。