Строительство школы
(Время: 1 сек. Память: 16 Мб Сложность: 30%)
В деревне Интернетовка все дома расположены вдоль одной улицы по одну сторону от нее. По другую сторону от этой улицы пока ничего нет, но скоро все будет – школы, магазины, кинотеатры и т.д.
Для начала в этой деревне решили построить школу. Место для строительства школы решили выбрать так, чтобы суммарное расстояние, которое проезжают ученики от своих домов до школы, было минимально.
План деревни можно представить в виде прямой, в некоторых целочисленных точках которой находятся дома учеников. Школу также разрешается строить только в целочисленной точке этой прямой (в том числе разрешается строить школу в точке, где расположен один из домов – ведь школа будет расположена с другой стороны улицы).
Напишите программу, которая по известным координатам домов учеников поможет определить координаты места строительства школы.
Входные данные
В первой строке входного файла INPUT.TXT сначала записано число N — количество учеников (1 ≤ N ≤ 100000). Во второй строке записаны в строго возрастающем порядке координаты домов учеников — целые числа, не превосходящие 2∙109 по модулю.
Выходные данные
В единственную строку выходного файла OUTPUT.TXT нужно вывести одно целое число — координату точки, в которой лучше всего построить школу. Если ответов несколько, выведите наибольший из них.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 4
1 2 3 4 | 3 |
| 2 | 3
-1 0 1 | 0 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
