solution

显然答案具有单调性，所以二分一个答案，也就是最后一个人到达的时间。

这样距离原点小于等于的点就都不用考虑了。然后目标就是放置一个传送门，使得其他的点与传送门之间的距离小于等于。显然将传送门放在这些点的中间最优秀。所以只要找到最靠右和最靠左的两个点，看他们之间的距离是不是小于等于即可。

code

/*
* @Author: wxyww
* @Date:   2020-04-17 18:59:02
* @Last Modified time: 2020-04-17 19:08:40
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
using namespace std;
typedef long long ll;
const int N = 100010;
ll read() {
    ll x = 0,f = 1;char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1; c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = x * 10 + c - '0'; c = getchar();
    }
    return x * f;
}
int a[N],n;
bool check(int x) {
    int l = 1e9,r = -1e9;
    for(int i = 1;i <= n;++i) {
        if(abs(a[i]) > x) {
            l = min(a[i],l);
            r = max(a[i],r);
        }
    }
    return (r - l + 1) / 2 <= x;
}
void solve() {
    n = read();
    for(int i = 1;i <= n;++i) a[i] = read();
    ll l = 0,r = 1e9,ans = 1e9;
    while(l <= r) {
        int mid = (l + r) >> 1;
        if(check(mid)) ans = mid,r = mid - 1;
        else l = mid + 1;
    }
    cout<<ans<<endl;

}
int main() {
    int T = read();
    while(T--) {
        solve();
    }

    return 0;
}