封闭图形个数
题号:NC309394
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

在蓝桥王国,数字的大小不仅仅取决于它们的数值大小,还取决于它们所形成的“封闭图形”的个数。

封闭图形是指数字中完全封闭的空间,例如数字 1, 2, 3, 5, 7 都没有形成封闭图形,而数字 0, 4, 6, 9 分别形成了 1 个封闭图形,数字 8 则形成了 2 个封闭图形。值得注意的是,封闭图形的个数是可以累加的。例如,对于数字 68,由于 6 形成了 1 个封闭图形,而 8 形成了 2 个,所以 68 形成的封闭图形的个数总共为 3

在比较两个数的大小时,如果它们的封闭图形个数不同,那么封闭图形个数较多的数更大。例如,数字 41 和数字 18,它们对应的封闭图形的个数分别为 1 和 2,因此数字 41 小于数字 18。如果两个数的封闭图形个数相同,那么数值较大的数更大。例如,数字 14 和数字 41,它们的封闭图形个数都是 1,但 14 < 41,所以数字 14 小于数字 41。如果两个数字的封闭图形个数和数值都相同,那么这两个数字被认为是相等的。

小蓝对蓝桥王国的数字大小规则十分感兴趣。现在,他将给你 n 个数 a_1, a_2, \dots, a_n,请你按照蓝桥王国的数字大小规则,将这 n 个数从小到大排序,并输出排序后的结果。

输入描述:

输入的第一行包含一个整数 n,表示给定的数字个数。

第二行包含 n 个整数 a_1, a_2, \dots, a_n,相邻整数之间使用一个空格分隔,表示待排序的数字。

输出描述:

输出一行包含 n 个整数,相邻整数之间使用一个空格分隔,表示按照蓝桥王国的数字大小规则从小到大排序后的结果。
示例1

输入

复制
3
18 29 6

输出

复制
6 29 18

说明

对于给定的数字序列 [18, 29, 6]
- 数字 18 的封闭图形个数为 0 + 2 = 2
- 数字 29 的封闭图形个数为 0 + 1 = 1
- 数字 6 的封闭图形个数为 1

按照封闭图形个数从小到大排序后,得到 [29, 6, 18](暂定顺序,需处理同圈数情况)。

由于数字 29 和数字 6 的封闭图形个数相同(均为 1),因此需要进一步按照数值大小对它们进行排序,最终得到 [6, 29, 18]

备注:

- 对于 50% 的评测用例,1 \le n \le 2 \times 10^3, 1 \le a_i \le 10^5
- 对于所有评测用例,1 \le n \le 2 \times 10^5, 1 \le a_i \le 10^9