만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

IQ

면접 대비

시간 제한1초메모리 제한64 MB

요약
2n개의 수를 n개의 짝으로 묶어 각 짝의 합 중 최댓값과 최솟값의 차이가 최소가 되도록 할 때, 그 최솟값을 출력한다.
난이도

쉬움10점 중 3점

유형
정렬, 그리디, 완전 탐색, 배열
정답자
아직 제출이 없습니다

문제

초보 학생 2n2n명이 알고리즘 연습에 참가했다. 각 학생은 IQ로 특징지어지며, ii번째 학생의 IQ는 a_ia\_i이다.

코치는 학생들을 두 명씩 팀으로 나누려고 한다. 각 팀은 팀원 IQ의 합인 팀 IQ로 특징지어진다. 예를 들어 학생 ii와 jj가 한 팀이 되면 팀 IQ는 a_i+a_ja\_i + a\_j이다. 팀 IQ가 더 큰 팀이 더 강하다.

코치의 생각에는 가장 강한 팀과 가장 약한 팀의 팀 IQ 차이가 최대한 작으면 연습이 훨씬 생산적이다. 가장 강한 팀과 가장 약한 팀의 팀 IQ 차이가 AA가 되도록 팀을 구성할 수 있는 최솟값 AA를 구해 코치를 도와라.

입력

첫째 줄에 정수 nn이 주어진다. (1≤n≤1001 \le n \le 100)

둘째 줄에 2n2n개의 정수가 주어지며, ii번째 정수는 ii번째 학생의 IQ a_ia\_i이다. (1≤a_i≤2001 \le a\_i \le 200, 1≤i≤2n1 \le i \le 2n)

출력

팀 구성이 가능한 최솟값 AA를 출력한다.

예제1

  1. 예제 1

    입력
    3
    100 100 89 140 102 150
    
    예상 출력
    38