[ARC180] E - LIS and Inversion

E - LIS and Inversion

Time Limit: 2 sec / Memory Limit: 1024 MB

分数：800分

题面

给定一个长度为的整数序列。
这里，保证对于每个，都有。

对于排列的得分和成本定义如下：

• 的得分是的最长递增子序列的长度。
• 的成本是满足以下条件的整数（）的数量：
  • 存在少于个整数，使得且。

对于每个，解决以下问题：

• 找到得分至少为的排列的最小成本。

限制条件

• 所有输入均为整数。

---

输入

从标准输入中以以下格式给出：

输出

按照顺序输出的答案。

---

输入样例 1

4
0 1 2 1

输出样例 1

0 0 1 3

对于每个，一个解如下：

• ：若，则得分为，成本为。
• ：若，则得分为，成本为。
• ：若，则得分为，成本为。
• ：若，则得分为，成本为。

---

输入样例 2

3
0 0 0

输出样例 2

0 0 0

---

输入样例 3

5
0 1 2 3 4

输出样例 3

0 1 2 3 4

---

输入样例 4

11
0 0 2 3 4 5 3 7 8 2 10

输出样例 4

0 0 0 1 2 3 4 5 7 8 9