B. Sorted Adjacent Differences

https://codeforces.com/contest/1339/problem/B

https://codeforces.com/blog/entry/75913

B. Sorted Adjacent Differences

You have array of n numbers a1,a2,…,an.

Rearrange these numbers to satisfy |a1−a2|≤|a2−a3|≤…≤|an−1−an|, where |x| denotes absolute value of x. It's always possible to find such rearrangement.

Note that all numbers in a are not necessarily different. In other words, some numbers of a may be same.

You have to answer independent t test cases.

Input

The first line contains a single integer t (1≤t≤104) — the number of test cases.

The first line of each test case contains single integer n (3≤n≤105) — the length of array a. It is guaranteed that the sum of values of n over all test cases in the input does not exceed 105.

The second line of each test case contains n integers a1,a2,…,an (−109≤ai≤109).

Output

For each test case, print the rearranged version of array a which satisfies given condition. If there are multiple valid rearrangements, print any of them.

Example

input

2

6

5 -2 4 8 6 5

4

8 1 4 2

output

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. 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. There are other possible answers like "2 4 8 1".

오름차순으로 정렬한다면, 기본적으로 첫 원소(인덱스가 0)와 마지막 원소(인덱스가 n-1)의 차이(절댓값)가 가장 클 것이다.

또한, 첫 원소가 음수, 양수, 마지막 원소가 음수, 양수와 상관 없이 마지막 원소가 첫 원소보다 앞에 오면 된다.

어차피 |마지막 원소 - 첫 원소| 차이의 절댓값이 가장 클 것이기 때문이다.

그 이후로 i = 1, j = n - 2, idx = n - 1 변수를 활용하여

1. 

v[i] v[j] v[idx]

2.

v[j] v[i] v[idx]

위의 2가지의 경우를 고려하여 적절하게 배치해준다.

조심해야할 것은 n이 홀수라면 마지막으로 남은 원소 하나를 신경써야 한다.

하지만

첨부한 두 번째 코드가 더 간단하다.

#include<bits/stdc++.h>
 
using namespace std;
 
#define Max 100002
 
int n;
 
int main()
{
    //freopen("C:\\Users\\park7\\Desktop\\buba.in.6", "r", stdin);
    cin.tie(0);
 
    int t = 0;
 
    scanf("%d", &t);
 
    for (int tc = 0; tc < t; tc++) {
        vector<int> v;
        int a[Max] = { 0 };
 
        scanf("%d", &n);
 
        int input;
        for (int i = 0; i < n; i++) {
            scanf("%d", &input);
            v.push_back(input);
        }
 
        sort(v.begin(), v.end());
 
        a[n - 2] = v[n - 1];
        a[n - 1] = v[0];
 
        int i = 1, j = n - 2, idx = n - 2;
 
        for (; i <= j; ++i, --j) {
            if (i == j && (n % 2)) {
                a[--idx] = v[i];
                continue;
            }
            else if (i == j) {
                break;
            }
 
            int d1 = abs(v[i] - v[j]);
            int d4 = abs(v[j] - a[idx]);
 
            int d2 = abs(v[j] - v[i]);
            int d3 = abs(v[i] - a[idx]);
 
            /*printf("i j idx\n");
            printf("v[%d] = %d, v[%d] = %d, v[%d] = %d\n", i, v[i], j, v[j], idx, v[idx]);
            printf("d1 = %d, d4 = %d, d2 = %d, d3 = %d\n", d1, d4, d2, d3);*/
 
            if (d1 <= d4) {
                // i j idx
                a[--idx] = v[j];
                a[--idx] = v[i];
            }
            else if (d2 <= d3) {
                // j i idx
                a[--idx] = v[i];
                a[--idx] = v[j];
            }
        }
 
        for (int i = 0; i < n; i++) {
            printf("%d ", a[i]);
        }
 
        printf("\n");
    }
 
    return 0;
}

#include<bits/stdc++.h>
 
using namespace std;
 
#define Max 100002
 
int n;
 
int main()
{
    //freopen("C:\\Users\\park7\\Desktop\\buba.in.6", "r", stdin);
    cin.tie(0);
 
    int t = 0;
 
    scanf("%d", &t);
 
    for (int tc = 0; tc < t; tc++) {
        vector<int> v, ans;
 
        scanf("%d", &n);
 
        int input;
        for (int i = 0; i < n; i++) {
            scanf("%d", &input);
            v.push_back(input);
        }
 
        sort(v.begin(), v.end());
 
        int i = 0, j = n - 1;
 
        for (; i <= j; ++i, --j) {
            if (i == j && (n % 2)) {
                ans.push_back(v[i]);
                continue;
            }
            else if (i == j) {
                break;
            }
 
            ans.push_back(v[i]);
            ans.push_back(v[j]);
        }
 
        for (int i = n - 1; i >= 0; i--) {
            printf("%d ", ans[i]);
        }
        printf("\n");
    }
 
    return 0;
}