将 $p_i\le n/2$ 看作 $-1$，否则看作 $1$。那么只需要把这个 $-1,1$ 序列排好序，变为 $-1,-1,-1,\cdots,1,1,1$，最后再进行一次 $FakeSort(1,n)$ 即可。

考虑怎么对一个区间进行排序，我们先考虑 $n\ge 8$ 的情况。此时只有 $-1,1,-1,1,\cdots,-1,1$ 或 $1,-1,1,-1,\cdots,1,-1$ 是无解的，原因显然，任何偶数长度区间中 $1$ 和 $-1$ 的个数相等，进行 $FakeSort$ 后序列不变。

剩下情况都有解。

定义 $Sort(l,r)$ 函数，要求区间 $[l,r]$ 内 $-1$ 和 $1$ 的个数不同。以 $-1$ 比 $1$ 多为例。

此时假设 $-1$ 和 $1$ 的个数差为 $2k$，那么先进行 $FakeSort(1,n)$，然后再进行一次 $FakeSort(l,r)$ 后，一般可以将后 $k$ 个 $-1$ 与前 $k$ 个 $1$ 交换位置。

此时后缀会有一段长度的 $1$。将后缀的偶数长度的 $1$ 删去，继续重复上面的流程，直到成功排序。

因为每次一般可以删除后缀 $\ge k$ 长度的 $1$，故每次 $k$ 会翻倍，所以只会调用 $2 \log n$ 次 $FakeSort$。

而因为 $Sort(l,r)$ 要求区间内 $-1$ 和 $1$ 的个数不同，所以不能直接排序。

假如我们能够找到一个前缀 $[1,i]$，满足前缀和的绝对值为 $2$，且至少有两个 $-1$，那么可以 $Sort(1,i)$，再 $Sort(3,n)$，使得序列成功排序。

而如果我们能够找到前缀和的绝对值为 $2$，但是没有两个 $-1$，要么只有两个 $1$，要么有一个 $-1$ 三个 $1$。

如果只有两个 $1$，因为 $n\ge 8$，$1$ 的个数至少为 $4$，所以后面也至少有两个 $1$。此时先 $Sort(i+1,n)$，再 $Sort(1,n-2)$ 即可排序。

如果有一个 $-1$ 三个 $1$，如果 $n\ge 10$，那么后面也至少有两个 $1$，先 $Sort(i+1,n)$ 再 $Sort(1,n-2)$ 也可以。但如果 $n=8$，那么 $Sort(1,4)$ 再 $Sort(5,8)$ 后序列就变成了 $-1,1,1,1,-1,-1,-1,1$，针对这个序列给出一个构造即可。

如果我们找不到前缀和的绝对值为 $2$，我们两个两个位置看，要么是 $-1,1$，要么是 $1,-1$，而每个奇数位置前缀和都是 $1$ 或 $-1$。只有其中一种正负性的前面证明了无解，其余情况，我们找到最远的一对前缀和分别为 $-1$ 和 $1$ 的位置 $x,y$（$x < y$），可以证明在 $n\ge 8$ 的情况下这两个位置差 $y-x\ge 4$，那么中间至少有一个 $-1$，一个 $1$。

$Sort(x+1,y)$ 后，如果 $x$ 位置前缀和为 $-1$，而 $x+1$ 位置的值肯定是 $-1$，所以 $x+1$ 位置前缀和绝对值为 $2$。如果 $y$ 位置前缀和为 $-1$，因为 $y$ 位置的值排序后肯定是 $1$，所以 $y-1$ 位置的前缀和绝对值为 $2$。

也就是说，进行上面的操作后，一定可以找到前缀和绝对值为 $2$ 的位置。

对于 $n\le 6$，可以直接乱搞。

操作次数为 $4\log n+O(1)$。