use std::{collections::HashMap, io::stdin};

const U:u32 = u32::MAX/4+1;
struct sparse_st<T:Ord+Copy> {
    h: HashMap<(u32,u32),T>
}
impl<T: Ord+Copy> sparse_st<T> {
    fn new() -> Self{
        Self {
            h:HashMap::new()
        }
    }
    fn insert(&mut self, i:u32, v: T) {
        let mut b = i;
        let mut l=1;
        while l<=U {
            let m = self.h.entry((b*l,(b+1)*l)).or_insert(v);
            *m=v.max(*m);
            l*=2;
            b/=2;
        }
    }
    fn query(&self, (mut a,mut b):(u32,u32))->Option<T> {
        let mut ans:Option<T> = None;
        let mut l = 1;
        while l<=U && a!=b{
            if a%2==1 {
                ans=ans.max(self.h.get(&(l*a,l*(a+1))).copied());
            }
            if b%2==1 {
                ans=ans.max(self.h.get(&(l*(b-1),l*b)).copied());
            }
            a=(a+1)/2;
            b=b/2;
            l*=2;
        }
        ans
    }
}
#[derive(PartialEq, Eq, Clone, Copy)]
struct reversed(u32);
impl PartialOrd for reversed {
    fn partial_cmp(&self, other: &Self) -> std::option::Option<std::cmp::Ordering> {
        let reversed(s)=self;
        let reversed(o)=other;
        o.partial_cmp(s)
    }
}
impl Ord for reversed {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        let reversed(s)=self;
        let reversed(o)=other;
        o.cmp(s)
    }
}
fn increase(A:&Vec<u32>) -> u32{
    let m=*A.iter().min().unwrap();
        let M = *A.iter().max().unwrap();
        let mut lo=0;
        let mut hi =M-m+1;
        while hi>lo+1 {
            let x = (hi+lo)/2;
            let mut st1=sparse_st::new();
            let mut st2=sparse_st::new();
            let mut st3=sparse_st::new();
            for (i,v) in A.iter().enumerate() {
                st1.insert(i as u32, v);
                st2.insert(*v, i as u32);
                st3.insert(*v, reversed(i as u32));
            }
            let reversed(a)=st3.query((m,m+x)).unwrap();
            let b=st2.query((m,m+x)).unwrap();
            let bv=st1.query((a,b)).unwrap();
            //println!("{:?}", (x,a,b,bv));
            if bv+x>M {
                hi=x;
            } else {
                lo=x;
            }
        }
        lo
}
pub fn main() {
    /*let mut st:sparse_st<u32> = sparse_st::new();
    st.insert(0,5);
    st.insert(1,4);
    st.insert(3,7);
    st.insert(2,0);
    for i in 0..4 {
        for j in i..5 {
            println!("{:?}", (i,j, st.query((i,j))));
        }
    }*/
    let mut s = String::new();
    stdin().read_line(&mut s);
    let t = s.trim().parse::<usize>().unwrap();
    for _ in 0..t {
        let mut s = String::new();
        stdin().read_line(&mut s);
        let mut s = String::new();
        stdin().read_line(&mut s);
        let v = s.trim().split(' ').map(|s| s.parse::<u32>().unwrap()).collect::<Vec<_>>();
        let m=*v.iter().min().unwrap();
        let M = *v.iter().max().unwrap();
        let x=increase(&v);
        let w=v.into_iter().map(|x| U-x).collect();
        let y= increase(&w);
        let z=x.max(y);
        println!("{}",M-m-z);
    }
}