Young한 에너지는 부족하다
시간 제한1초메모리 제한256 MB
3N개의 나이를 N개의 세 명 묶음으로 나누고, 각 묶음의 에너지를 중간 나이로 정의할 때, 에너지 최댓값과 최솟값의 차이를 최소화한다.
문제
대한민국 최고의 스트릿 알고리즘 크루를 찾기 위한 리얼리티 서바이벌 <스트릿 알고리즘 파이터>! 전국에서 알고리즘을 잘한다는 명의 대학생들이 참여했고, 이들은 3명씩 개의 크루를 이루어 스트릿 알고리즘 배틀을 벌이게 된다.
하지만 컴퓨터공학도들은 언제나 혼자 코딩을 해왔기 때문에 제작진이 크루를 만들어주어야 한다...
제작진은 혹시나 young한 에너지가 부족한 크루가 생기지 않을까 걱정하고 있다. 그래서 제작진은 아래와 같은 점을 고려해 개의 크루를 구성하려 한다.
- 크루원의 연령의 중간값, 즉 세 명 중 두번째로 연령이 높은 크루원의 연령을 크루의 에너지라 부르자.
- 제작진은 가장 에너지가 높은 크루와 가장 에너지가 낮은 크루의 에너지 차이를 최소화해야 한다.
최소화한 값을 구하라.
입력
첫째 줄에 이 주어진다. 참가자는 총 명이다.
둘째 줄에 개의 정수가 공백을 사이에 두고 주어진다. 번째 정수 는 번째 참가자의 연령이다.
출력
명의 참가자로 크루 개를 적절히 구성해, 가장 에너지가 높은 크루와 가장 에너지가 낮은 크루의 에너지 차이를 최소화했을 때의 에너지 차이 값을 출력하라.