Given N numbers, X1, X2, … , XN, let us calculate the difference of every pair of numbers: ∣Xi - Xj∣ (1 ≤ i ＜ j ≤ N). We can get C(N,2) differences through this work, and now your task is to find the median of the differences as quickly as you can!

Note in this problem, the median is defined as the (m/2)-th smallest number if m,the amount of the differences, is even. For example, you have to find the third smallest one in the case of m = 6.

Input
The input consists of several test cases.
In each test case, N will be given in the first line. Then N numbers are given, representing X1, X2, … , XN, ( Xi ≤ 1,000,000,000 3 ≤ N ≤ 1,00,000 )

Output
For each test case, output the median in a separate line.

Sample
Input
4
1 3 2 4
3
1 10 2
Output
1
8

//(二分)
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int n;
long long a[N];
int ch(int mid)
{
    int res=0,q;
  for(int i=1,j=0;i<n;i++)
  {

    while(a[i]-a[j]>mid)
    j++;
    res+=i-j;//将小于mid的数进行统计 
  }
  q=n*(n-1)/2;
  q=(q+1)/2;//如果为偶数加一，int型下取整，而偶数+1为奇数，也是下取整 
  if(res>=q)//如果mid之前的两个数之间的差值的个数大于所有的差值的个数 
  return true;//说明mid取大了 
  else
  return false;
} 
int main()
{
    while(~scanf("%d",&n))
    {
    for(int i=0;i<n;i++)
    cin>>a[i];
    sort(a,a+n);//将输入的数进行排序 
    long long l=0,r=a[n-1]-a[0];//上界为所有差值里面最大的一个数 
    int sum;
    while(l<=r)
    {
      int mid=(l+r)/2;//从0~a[n-1]-a[0]最大的数中求中间值mid(因为a[n-1]-a[0]是所有数中最大的) 
      if(ch(mid))
      {
        sum=mid;
        r=mid-1;//mid取大了，则向下调整上界r 
      }
      else
      l=mid+1;
    }
    cout<<sum<<endl;
   }
    return 0;
}