import Control.Arrow
import Control.Monad
import Data.List
import qualified Data.ByteString.Char8 as B
import Data.Ord

main :: IO ()
main = readLn >>= main'
    where
        main' n = readLine >>= printRes . solve n
        printRes = putStrLn . unwords . map show

solve :: Int -> [Int] -> [Int]
solve n = head . check n . sortBy (flip compare)
    where
        check l (x : y : zs) = [x, search (l - 1) hx $ y : zs] : check (l - 1) (y : zs)
            where
                hx = x `div` 2
        check _ _ = []

        search l x xs
            | l == 1 = head xs
            | l == 2 = head $ sortBy cmpf xs
            | x > z = search hl x ys
            | x < z = search (l - hl - 1) x zs
            | otherwise = x
            where
                hl = l `div` 2
                (ys, z : zs) = splitAt hl xs
                cmpf = comparing (abs . (hl -))


readLine :: IO [Int]
readLine = unfoldr (\s -> second (maybe B.empty snd . B.uncons) <$> B.readInt s) <$> B.getLine

readContents :: Int -> IO [[Int]]
readContents = flip replicateM readLine