Different Medians

Chef is given an integer $N$. Chef wants to construct a [permutation](https://en.wikipedia.org/wiki/Permutation) $A = [A_1, A_2, \ldots, A_N]$ of $\{1, 2, 3, \ldots, N \}$ that satisfies the following condition: - Let $P_i$ denote the prefix of $A$ of length $i$, i.e, $P_i = [A_1, A_2, \ldots, A_i]$. Then, for every $1 \leq i \lt N$, it must hold that $\text{median}(P_i) \neq \text{median}(P_{i+1