같은 탑
시간 제한2초메모리 제한512 MB
최대 50개의 블록(총합 500,000 이하)으로 두 개의 탑을 쌓아 높이가 같도록 만들 때 가능한 최대 높이를 구하고, 불가능하면 -1을 출력합니다.
문제
홍준이는 N개의 직사각형 블록을 가지고 있다. 블록 위에 다른 블록을 올려 탑을 만들 수 있다.
홍준이는 높이가 같은 두 개의 탑을 만들려고 한다. 각 탑에는 적어도 하나의 블록이 들어가야 한다. 두 탑의 공통 높이는 가능한 한 커야 하며, 모든 블록을 사용할 필요는 없다.
각 블록의 높이가 주어질 때 만들 수 있는 두 탑의 최대 공통 높이를 구하시오.
입력
첫째 줄에 블록의 개수 N이 주어진다. N은 50 이하의 자연수이다.
둘째 줄에 각 블록의 높이가 주어진다. 각 높이는 500,000 이하의 자연수이고, 모든 블록의 높이의 합은 500,000을 넘지 않는다.
출력
만들 수 있는 두 탑의 최대 공통 높이를 출력한다.
높이가 같은 두 개의 비어 있지 않은 탑을 만들 수 없다면 -1을 출력한다.