시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 79 21 18 32.143%

문제

국회에는 당이 N개 있고, 각각의 당은 확보한 의석이 있다.

이번에 당끼리 연합을 맺기로 했다. 연합이 유효하려면, 연합에 속한 당의 의석의 합이 전체 의석의 반을 넘어야 한다.

유효한 연합에서 소속된 당 하나를 제거했을 때, 여전히 유효한 연합이라면, 그 연합을 깔끔하지 못한 연합이라고 한다. 유효한 연합 중에서 깔끔하지 못한 연합을 제외한 것을 깔끔한 연합이라고 한다. 깔끔한 연합 중, 포함하는 의석의 수가 가장 많은 것을 찾는 프로그램을 작성하시오.

입력

첫째 줄에 당의 수 N (1 ≤ N ≤ 300), 둘째 줄에 각 당의 의석 수가 주어진다.

당의 번호는 1번부터 N번까지이며, 의석 수의 합은 100,000을 넘지 않는다.

출력

의석 수가 가장 많은 깔끔한 연합을 구한 다음, 첫째 줄에 당의 수, 둘째 줄에 당의 번호를 출력한다.

예제 입력

4
1 3 2 4

예제 출력

2
2 4

힌트

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2008 1번