数组4-5重排

题目背景

在一次数据整理任务中，你需要对一个特殊的数字序列进行重新排列。这个序列中的数字需要满足一个特定的模式，以确保数据的正确性和可用性。

题目描述

（这是 fix34 问题的稍难版本。）给定一个数组，返回一个包含与给定数组完全相同数字的数组，但经过重新排列，使得每个 $4$ 后面都紧跟着一个 $5$。不要移动 $4$ 的位置，但其他所有数字都可以移动。数组中 $4$ 和 $5$ 的数量相同，并且每个 $4$ 后面都有一个不是 $4$ 的数字。在此版本中，$5$ 可以出现在原始数组的任何位置。

输入格式

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

一个整数数组，表示原始序列。

输出格式

输出以如下格式输出到标准输出中。

一个整数数组，表示重新排列后的序列。

样例

[5 4 9 4 9 5]

[9, 4, 5, 4, 5, 9]

[1 4 1 5]

[1, 4, 5, 1]

[1 4 1 5 5 4 1]

[1, 4, 5, 1, 1, 4, 5]

样例解释

对于样例1：原始数组为 [5, 4, 9, 4, 9, 5]。其中 $4$ 位于索引 $1$ 和 $3$。我们需要将 $5$ 放置在 $4$ 之后。原始数组中，索引 $0$ 和 $5$ 处的 $5$ 是“自由”的（即它们前面没有 $4$）。索引 $2$ 和 $4$ 处的 $9$ 需要被移动，以便为 $5$ 腾出位置。最终，索引 $0$ 处的 $5$ 被移动到索引 $2$ 处，索引 $5$ 处的 $5$ 被移动到索引 $4$ 处。原来索引 $2$ 和 $4$ 处的 $9$ 则分别被移动到索引 $0$ 和 $5$ 处，得到 [9, 4, 5, 4, 5, 9]。

数据范围

每个测试用例的时间限制为 $1$ 秒，内存限制为 $1024$ KiB。