페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8573

모임 장소 1s 1024MB

문제

N 명의 사람들이 수직선 위에 살고 있다.

사람들의 집의 좌표를 각각 x_1, x_2, ..., x_N 이라고 하자.

이 N 명의 집 중에서 하나를 골라, 여기에 모든 사람들이 모일 것이다.

x = a 인 곳에서 x = b 인 곳으로 이동하는 비용은 |~a -b~| 이다. ( 절댓값 기호 )

예를 들어, x = 2 에서 x = 9 로 이동하는 비용은 |~2 - 9~| = 7 이다.

반대로, x = 9 에서 x = 2 로 이동하는 비용도 |~9- 2~| = 7 이다.

어떤 집에서 모여야, 사람들의 이동 비용의 합이 최소인지 출력하자.


입력

첫 줄에 N 이 입력된다. ( 1 ≤ N ≤ 100,000 )

이후 x_1, x_2, ..., x_N 이 입력된다. ( 모두 10^9 이하의 자연수 )

이들끼리는 값이 중복될 수도 있다.


출력

사람들의 이동 비용의 합이 최소가 되려면,

어떤 x 좌표에서 모여야 하는지 출력하자.

만약 가능한 x 값이 여러 개라면, 그들을 오름차순으로 출력해야 한다.


예제 #1

5
6 3 1 9 7
6

x = 6 에서 모이면, 비용의 합은 |6 - 6 | + | 6 - 3 | + | 6 - 1 | + | 6 - 9 | + | 6 - 7 | = 12 이다.

x = 1 에서 모이면, 비용의 합은 | 1 - 6 | + | 1 - 3 | + | 1 - 1 | + | 1 - 9 | + | 1 - 7 | = 21 이다.

이외에, x = 3, 7, 9 에서 모여도 비용의 합은 모두 x = 6 일 때의 비용인 12 보다 클 것이다.


예제 #2

8
5 2 3 4 5 3 7 6
4 5

예제 #3

6
1 2 3 1 2 3
2

예제 #4

8
3 3 1 7 3 3 3 8
3



출처

againalgo
로그인해야 코드를 작성할 수 있어요.