Rearrange Array: 4 Followed by 5

Background

In a data organization task, you are required to rearrange a special sequence of numbers. The numbers in this sequence need to conform to a specific pattern to ensure data correctness and usability.

Problem Description

(This is a slightly harder version of the fix34 problem.) Return an array that contains exactly the same numbers as the given array, but rearranged so that every $4$ is immediately followed by a $5$. Do not move the $4$'s, but every other number may move. The array contains the same number of $4$'s and $5$'s, and every $4$ has a number after it that is not a $4$. In this version, $5$'s may appear anywhere in the original array.

Input Format

Input is given from standard input in the following format.

An integer array, representing the original sequence.

Output Format

Output is printed to standard output in the following format.

An integer array, representing the rearranged sequence.

Sample

[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]

Sample Explanation

For Sample 1: The original array is [5, 4, 9, 4, 9, 5]. Here, $4$s are at indices $1$ and $3$. We need to place $5$s after the $4$s. In the original array, the $5$s at indices $0$ and $5$ are "free" (i.e., they are not preceded by a $4$). The $9$s at indices $2$ and $4$ need to be moved to make space for $5$s. Ultimately, the $5$ at index $0$ is moved to index $2$, and the $5$ at index $5$ is moved to index $4$. The original $9$s at indices $2$ and $4$ are moved to indices $0$ and $5$ respectively, resulting in [9, 4, 5, 4, 5, 9].

Constraints

Time limit: $1$s, Memory limit: $1024$ KiB for each test case.