#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <stack>
#include <sstream>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <ctime>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <list>
#include <set>
#include <map>
#include <iostream>
using namespace std;

//--------------------------------------------
#define SZ(x) ((int)x.size())
#define pb(x) push_back(x)
#define mp(a, b) make_pair(a, b)
#define ALL(X) X.begin(), X.end()
#define SRT(x) sort(ALL(x))
#define RVRS(x) reverse(ALL(x))
#define FILL(x, value) memset(x, value, sizeof(x))

#define next next1
#define hash hash1
#define rank rank1

#ifdef _DEBUG_
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define eprintf(...)
#endif

#if((_WIN32 || __WIN32__) && __cplusplus < 201103L)
    #define LLD "%I64d"
#else
    #define LLD "%lld"
#endif

template <class T> inline void check_max(T& actual, T check) {
    if(actual < check) {
        actual = check;
    }
}

template <class T> inline void check_min(T& actual, T check) {
    if(actual > check) {
        actual = check;
    }
}

const double EPS = 1e-9;
const int IINF = 1000000000;
const double PI = acos(-1.0);
const long long LINF = 6000000000000000000LL;
//--------------------------------------------

namespace Solution {

const int maxN = (int)2e5 + 10;

int n, a[maxN];

void cleanup() {

}

bool Read() {
    cleanup();
    if(scanf("%d", &n) == 1) {
      for(int i = 0; i < n; ++i) {
        scanf("%d", a + i);
      }
      return true;
    }
    return false;
}

int get_short_best(set<int>& s) {
  int k = *s.begin();
  s.erase(s.begin());
  int val = *s.rbegin() - *s.begin();
  s.insert(k);
  int k1 = *s.rbegin();
  s.erase(k1);
  int val1 = *s.rbegin() - *s.begin();
  s.insert(k1);
  if(val > val1) {
    return k1;
  }
  return k;
}

vector< tuple<int, int, int> > added;
vector< tuple<int, int, int> > removed;

int get_min_with_erase(int p, set< tuple<int, int, int> >& st, set<int>& positions, bool apply_changes) {
  set<int>::iterator itp = positions.find(p);
  set<int>::iterator ktp = itp;
  added.resize(0);
  removed.resize(0);
  if(itp != positions.begin()) {
    --itp;
    removed.pb(make_tuple(p - *itp, p, *itp));
    st.erase(removed.back());
  }
  else {
    itp = positions.end();
  }
  ++ktp;
  if(ktp != positions.end()) {
    removed.pb(make_tuple(*ktp - p, *ktp, p));
    st.erase(removed.back());
  }
  if(itp != positions.end() && ktp != positions.end()) {
    st.insert(make_tuple(*ktp - *itp, *ktp, *itp));
    added.pb(make_tuple(*ktp - *itp, *ktp, *itp));
  }
  positions.erase(p);
  int ret = get<0>(*st.begin());
  if(!apply_changes) {
    positions.insert(p);
    for(int i = 0; i < SZ(added); ++i) {
      st.erase(added[i]);
    }
    for(int i = 0; i < SZ(removed); ++i) {
      st.insert(removed[i]);
    }
  }
  return ret;
}

void Run() {
  int turn = 0;
  set<int> positions;
  set< tuple< int, int, int > > st;
  sort(a, a + n);
  for(int i = 0; i < n; ++i) {
    positions.insert(a[i]);
  }
  for(int i = 1; i < n; ++i) {
    st.insert(make_tuple(a[i] - a[i - 1], a[i], a[i - 1]));
  }
  while(SZ(positions) > 2) {
    if(turn == 0) { // maximum is minimized
      int removal = get_short_best(positions);
      if(removal == *positions.begin()) {
        set<int>::iterator it = positions.begin();
        ++it;
        st.erase(make_tuple(*it - removal, *it, removal));
        positions.erase(removal);
      }
      else {
        set<int>::iterator it = positions.find(removal);
        --it;
        st.erase(make_tuple(removal - *it, removal, *it));
        positions.erase(removal);
      }
    }
    else { // minimum is maximized
      tuple<int, int, int> tp = *st.begin();
      int v = get_min_with_erase(get<1>(tp), st, positions, false);
      int w = get_min_with_erase(get<2>(tp), st, positions, false);
      if(v < w) { // better remove w
        get_min_with_erase(get<2>(tp), st, positions, true);
      }
      else {
        get_min_with_erase(get<1>(tp), st, positions, true);
      }
    }
    turn ^= 1;
  }

  printf("%d\n", *positions.rbegin() - *positions.begin());
}

} // Solution

namespace StressTest {

long long GetTime() {
    srand(time(NULL));
    return rand() << 16LL;
}

void GenerateInput() {
    FILE* output = fopen("input.txt", "w");
    srand(GetTime());


    fclose(output);
}

void BruteForce() {
    FILE* input = fopen("input.txt", "r");
    FILE* output = fopen("brute.out", "w");

    fclose(input);
    fclose(output);
}

} // StressTest

int main() {
#ifdef _DEBUG_
    int test_id = 0;
//    StressTest::GenerateInput();
//    StressTest::BruteForce();
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    while(Solution::Read()) {
#ifdef _DEBUG_
        clock_t startTime = clock();
        eprintf("Begin of test #%d:\n", ++test_id);
#endif

        Solution::Run();

#ifdef _DEBUG_
        clock_t endTime = clock();
        eprintf("Time consumed for test #%d is %lf\n", test_id, (double)(endTime - startTime) / (double)CLOCKS_PER_SEC);
#endif
    }
    return 0;
}