排列修补

题目描述

给定一个长度为 $n$ 的数组 $a = \{a_1, a_2, \dots, a_n\}$。

对于每个前缀 $\{a_1, a_2, \dots, a_i\}$（其中 $1 \le i \le n$），你需要计算将其去重以后,“补全”为一个排列所需插入的最少元素数量。

补全规则如下：

• 目标是得到一个长度为 $m$ 的排列，即包含从 $1$ 到 $m$ 的所有整数，且每个整数恰好出现一次。
• $m$ 的值必须不小于该前缀中的任何元素，即 $m \ge \max(a_1, a_2, \dots, a_i)$。
• 在所有可选的 $m$ 中，你需要选择一个能使插入元素数量最少的 $m$。

请对每个前缀，都计算出这个最少需要插入的元素数量。

输入格式

第一行输入一个整数 $n$，表示数组的长度。

第二行输入 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示数组的元素。

输出格式

输出一行，包含 $n$ 个用空格分隔的整数。其中第 $i$ 个整数表示对前缀 $\{a_1, a_2, \dots, a_i\}$ 进行补全所需的最少元素数。

样例

样例输入 1

3
3 1 6

样例输出 1

2 1 3

样例输入 2

5
1 2 3 4 5

样例输出 2

0 0 0 0 0

提示

样例 1 说明

• 对于前缀 {3}:
  • 集合中元素为 $\{3\}$，最大值为 $3$。最优的目标排列长度 $m=3$。
  • 目标排列为 $\{1, 2, 3\}$。需要插入 $\{1, 2\}$，共 2 个元素。
• 对于前缀 {3, 1}:
  • 集合中不同元素为 $\{1, 3\}$，最大值为 $3$。最优的目标排列长度 $m=3$。
  • 目标排列为 $\{1, 2, 3\}$。需要插入 $\{2\}$，共 1 个元素。
• 对于前缀 {3, 1, 6}:
  • 集合中不同元素为 $\{1, 3, 6\}$，最大值为 $6$。最优的目标排列长度 $m=6$。
  • 目标排列为 $\{1, 2, 3, 4, 5, 6\}$。需要插入 $\{2, 4, 5\}$，共 3 个元素。

数据范围与约定

对于 $100\%$ 的数据，保证：

• $1 \le n \le 2 \times 10^5$
• $1 \le a_i \le 10^9$