N개의 수가 있다.

이 중에 어느 한 수가 N/2개 이상 존재할 때 이 수를 다수파라고 한다.

예를 들어 다음과 같이 9개의 수가 있다면

1 2 1 5 7 1 3 1 1

9개의 숫자 중에서 1이 5개이므로 1이 다수파라고 할 수 있다.

N과 N개의 수가 주어질 때 다수파가 존재하는지 결정하고, 만약 존재한다면 그 수가 무엇인지 찾아 출력하는 프로그램을 작성하시오.

문제출제 : 한양대학교 소프트웨어학과 서상우

첫 번째 줄에는 N이 주어지고 그 다음 줄에 서로 다른 N개의 정수가 사이에 한 칸의 공백을 두고 주어진다. N은 1,000 이하의 자연수이며 주어지는 수는 int의 범위를 넘지 않는다.

다수파가 존재한다면 첫 줄에 1을 출력하고 존재하지 않는다면 첫 줄에 0을 출력한다. 다수파 존재한다면 이어 두 번째 줄에 다수파인 수를 다수파인 수를 출력한다.