This problem is very similar to “2-Way Partition”, but now the goal is to partition an input array more carefully.

Given: A positive integer $n \le 10^5$ and an array $A[1..n]$ of integers from $-10^5$ to $10^5$.

Return: An array $B[1..n]$ such that it is a permutation of $A$ and there are indices $1 \le q \le r \le n$ such that
$B[i] < A[1]$ for all $1 \le i \le q-1$, $B[i]=A[1]$ for all $q \le i \le r$, and $B[i] > A[1]$ for all $r+1 \le i \le n$.