Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register
ACM-ICPC亚洲区预选赛(北京赛区)游戏对抗邀请赛​正在报名中

Language:
Median
 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 6032 Accepted: 2022

Description

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
```

Sample Output

```1
8```

Source

[Submit]   [Go Back]   [Status]   [Discuss]