You are given n points on a line with their coordinates x i. Find the point x so the sum of distances to the given points is minimal.
Input
The first line contains integer n (1 ≤ n ≤ 3·105) — the number of points on the line.
The second line contains n integers x i ( - 109 ≤ x i ≤ 109) — the coordinates of the given n points.
Output
Print the only integer x — the position of the optimal point on the line. If there are several optimal points print the position of the leftmost one. It is guaranteed that the answer is always the integer.Exampleinput
4
1 2 3 4
output
2
Solution:
#include <bits/stdc++.h> using namespace std; int a[1234567]; int main() { int n; scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", a + i); } sort(a, a + n); printf("%d\n", a[(n - 1) / 2]); return 0; }
Related posts:
Modular Multiplicative Inverse
Wilbur and Array
Unusual Graph
Maximum Reduction
Attack on Red Kingdom
New Year Ratings Change
Decreasing Debts
Metro
Packmen
Magic Grid
Cow and Treats
Bad Ugly Numbers
2 - SAT
Invertation in Tournament
Bad Days
Construct the String
Gambling Nim
Gotta Catch Em' All!
Perfect Triples
Monopole Magnets
Middle Class
Circle of Monsters
Serega and Fun
Traveling Around the Golden Ring of Berland
Product transformation
The Holmes Children
Social Network
Palindrome
New Year Candles
Wilbur and Strings
Finding Power of Factorial Divisor
Pumping Stations