#include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<cmath>

 #include<cstring>

 using namespace std;

 typedef long long ll;

 const ll INF = 1e9 + ;

 const int maxn = 1e6 + ;

 ll a[maxn], n, m;

 ll ok(ll mid)

 {

     ll ans = ;

     for(int i = ; i < n; i++)//此处不等于n是由于到了n没有比它更大的了，加上=也无妨

     {

         if(a[i] + mid >= a[n])//可以加速一点

         {

             ans += n - i;

             continue;

         }

         int t = upper_bound(a + i, a + n + , a[i] + mid) - a;//这里用区间a+i而不是a+1可以加速求解

         ans += t -  - i;

     }

     return ans;

 }

 int main()

 {

     while(scanf("%lld", &n) != EOF)

     {

         for(int i = ; i <= n; i++)scanf("%lld", &a[i]);

         sort(a + , a + n + );

         m = n * (n - ) / ;

         m = (m + ) / ;//求出第m个

         ll l = , r = a[n] - a[], ans;

         while(l <= r)

         {

             ll mid = (l + r) / ;

             if(ok(mid) >= m)//小于等于mid的数字个数 >= m 说明mid>=最优解

             {

                 ans = mid;

                 r = mid - ;

             }

             else l = mid + ;

         }

         printf("%lld\n", ans);

     }

     return ;

 }