提示: 欢迎访问OurACM平台。
Problem 1891 升降序列

Accept: 672    Submit: 1523
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

升降序列的定义如下:给定N个不同的整数a1,a2,…,aN组成的集合,其中N为奇数,在这N个整数集合的一个排列中,如果对于所有1<i<N,i为偶数,都有ai-1 < ai > ai+1,那么称该序列为升降序列。
给定N个不同的整数组成的集合,请你构造出一个升降序列,使得该升降序列的字典序最小。
对于有N个元素的两个整数序列A和B,如果存在下标k,使得Ak<Bk,并且对于所有1≤i<k≤N,都有Ai=Bi,那么称序列A的字典序小于序列B;如果存在下标k,使得Ak>Bk,并且对于所有1≤i<k≤N,都有Ai=Bi,那么称序列A的字典序大于序列B;如果不存在下标k,使得Ak≠Bk(1≤k≤N),那么称序列A的字典序等于序列B。

Input

输入数据第一行为一整数T,表示有T组输入数据。每组输入数据的第一行为一个整数N(1≤N≤50,000,N为奇数),以下一行为N个不同的整数ai(0≤ai≤1,000,000,1≤i≤N),表示集合中的每一个元素。

Output

对于每组数据,输出字典序最小的升降序列,每个元素之间请用一个空格分开。

Sample Input

2 3 1 2 3 5 100 350 200 101 401

Sample Output

1 3 2 100 200 101 401 350

Source

福州大学第七届程序设计竞赛

Submit  Back  Status  Discuss