Given an array $$$a$$$ of length $$$n$$$ $$$(1 \le n \le 10^5)$$$ $$$(1 \le a_i \le 10^9)$$$. Initially, you are at index $$$1$$$ and you want to go to index $$$n$$$ and visit every index exactly once.
You can jump from your current index $$$i$$$ to another index $$$j$$$ if and only if the absolute difference doesn't exceed 2, that is $$$|i - j| \le 2$$$.
You also have an array $$$b$$$, that initially contains one element $$$a_1$$$. When you jump to a new index $$$j$$$, you mark it as visited and put $$$a_j$$$ at the end of the array $$$b$$$.
Your task is to print the lexicographically minimum array $$$b$$$ that can be obtained after a valid walk, that is after visiting all indices and ending at index $$$n$$$.
The first line contains a single integer $$$t$$$ $$$(1 \le t \le 10^5)$$$, the number of test cases.
The first line of each test case contains a single integer $$$n$$$ $$$(1 \le n \le 10^5)$$$, the length of the array $$$a$$$.
The second line of each test case contains $$$n$$$ integers $$${a_1,\space a_2,\dots,\space a_n}$$$ $$$(1 \le a_i \le 10^9)$$$, the elements of the array $$$a$$$.
It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$10^5$$$.
For each test case, print $$$n$$$ space separated integers $$${b_1, \space b_2, \dots ,\space b_n}$$$, the elements of array $$$b$$$, that is the lexicographically minimum array that can be obtained after a valid walk.
333 2 144 3 1 273 1 1 2 3 2 1
3 2 1 4 1 3 2 3 1 1 2 2 3 1
