You have array of nn numbers a1,a2,…,ana1,a2,…,an.
Rearrange these numbers to satisfy |a1−a2|≤|a2−a3|≤…≤|an−1−an||a1−a2|≤|a2−a3|≤…≤|an−1−an|, where |x||x| denotes absolute value of xx. It‘s always possible to find such rearrangement.
Note that all numbers in aa are not necessarily different. In other words, some numbers of aa may be same.
You have to answer independent tt test cases.
Input
The first line contains a single integer tt (1≤t≤1041≤t≤104) — the number of test cases.
The first line of each test case contains single integer nn (3≤n≤1053≤n≤105) — the length of array aa. It is guaranteed that the sum of values of nn over all test cases in the input does not exceed 105105.
The second line of each test case contains nn integers a1,a2,…,ana1,a2,…,an (−109≤ai≤109−109≤ai≤109).
Output
For each test case, print the rearranged version of array aa which satisfies given condition. If there are multiple valid rearrangements, print any of them.
Example
input
Copy
2
6
5 -2 4 8 6 5
4
8 1 4 2
output
Copy
5 5 4 6 8 -2
1 2 4 8
Note
In the first test case, after given rearrangement, |a1−a2|=0≤|a2−a3|=1≤|a3−a4|=2≤|a4−a5|=2≤|a5−a6|=10|a1−a2|=0≤|a2−a3|=1≤|a3−a4|=2≤|a4−a5|=2≤|a5−a6|=10. There are other possible answers like "5 4 5 6 -2 8".
In the second test case, after given rearrangement, |a1−a2|=1≤|a2−a3|=2≤|a3−a4|=4|a1−a2|=1≤|a2−a3|=2≤|a3−a4|=4. There are other possible answers like "2 4 8 1".
找中位数
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <queue>
#include <map>
#include <sstream>
#include <cstdio>
#include <cstring>
#include <numeric>
#include <cmath>
#include <iomanip>
#include <deque>
#include <bitset>
//#include <unordered_set>
//#include <unordered_map>
//#include <bits/stdc++.h>
//#include <xfunctional>#define ll long long
#define PII pair<int, int>
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define dec(i,a,b) for(ll i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
usingnamespace std;
int dir[5][2] = { { 0,1 } ,{ 0,-1 },{ 1,0 },{ -1,0 } ,{ 0,0 } };
constlonglong INF = 0x7f7f7f7f7f7f7f7f;
constint inf = 0x3f3f3f3f;
constdouble pi = 3.14159265358979;
constint mod = 1e9 + 7;
constint N = 1000;
//if(x<0 || x>=r || y<0 || y>=c)
//1000000000000000000
inline ll read()
{
ll x = 0; bool f = true; char c = getchar();
while (c < ‘0‘ || c > ‘9‘) { if (c == ‘-‘) f = false; c = getchar(); }
while (c >= ‘0‘ && c <= ‘9‘) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
return f ? x : -x;
}
bool cmp(PII a,PII b)
{
return a.second < b.second;
}
int main()
{
int T;
cin >> T;
while (T--)
{
int n;
cin >> n;
vector<ll> a(n);
rep(i, 0, n)
{
cin >> a[i];
}
sort(a.begin(), a.end());
int R = n / 2,L=R-1;
for (int l = L,r=R; l >= 0 && r<n; r++,l--)
{
cout << a[r] << ""<<a[l]<<"";
}
if (n % 2)
{
cout << a[n - 1];
}
cout << endl;
}
return0;
}
