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:
Packets
Cunning Gena
Felicity is Coming!
Invertation in Tournament
Heavy-light decomposition
Rotate Columns (easy version)
Giving Awards
Intellectual Inquiry
PE Lesson
Kuroni and Impossible Calculation
Optimal Subsequences (Easy Version)
Paint it really, really dark gray
Travel Card
Pudding Monsters
Generate a String
New Year and Social Network
Prince's Problem
Double Elimination
Xenia and Hamming
Range Minimum Query
Antipalindrome
Gotta Go Fast
Dreamoon Likes Coloring
Wonder Room
Stars and bars
Quiz
The Art of Dealing with ATM
Au Pont Rouge
Zuma
Divide and Conquer DP
Block Towers
Attack on Red Kingdom