在“数字阵列”中摆放着一列能量晶石，共有 `n` 块，第 `i` 块晶石上刻着一个正整数能量值 `a[i]`。小慕要对这列晶石进行一次“”，规则如下： - 若某块晶石的能量值是完全平方数，则称其为“辉晶石”。完全平方数满足：存在整数 `k` 使得 `x = k*k`。 - 所有辉晶石所在的位置集合保持不变，只在这些位置上把对应的数按 升序 重新填回。 - 其余晶石称为“暗晶石”（非完全平方数）。 - 所有暗晶石所在的位置集合保持不变，只在这些位置上把对应的数按 降序 重新填回。 你需要输出重排完成后的整列能量晶石数值。
提示：带虚线的词点一下有通俗解释。
输入描述
第一行输入一个整数 `n`，表示魔纹石数量。 第二行输入 `n` 个整数 `a[0], a[1], ..., a[n-1]`，表示从左到右的能量值。 - `1 <= n <= 100` - `1 <= a[i] <= 1000`
输出描述
输出一行 `n` 个整数，表示按规则重排后的数组。
示例
示例 1
输入
8 36 11 4 18 49 7 10 9
输出
4 18 9 11 36 10 7 49
说明：位置 `0,2,4,7` 上的数为完全平方数：`36 (=6*6)`, `4 (=2*2)`, `49 (=7*7)`, `9 (=3*3)`。 只在这些位置上按升序回填后变为：`4, 9, 36, 49`，对应放回位置 `0,2,4,7`。 其余位置 `1,3,5,6` 上的数为非完全平方数：`11,18,7,10`。 只在这些位置上按降序回填后变为：`18, 11, 10, 7`，对应放回位置 `1,3,5,6`。
时间限制 1000 ms · 内存限制 128 MB