문제
형제 사이인 최대치(이하 대치)와 최소치(이하 소치)가 게임을 한다. N개의 정수가 주어지고 소치부터 게임을 시작한다.
* 소치가 N개의 정수 중에서 최소값을 찾고 그 다음 최소값으로 교환한다. * 대치가 N개의 정수 중에서 최대값을 찾고 그 다음 최대값으로 교환한다. * N개의 정수 중에 서로 다른 종류의 수가 2가지 이하라면 현재 차례의 사람은 게임에서 패하게 되며 게임이 종료된다.
예를 들어 4개의 수 3 1 2 1 이 주어졌다고 하자. 먼저 소치가 최소값 1을 찾아 다음 최소값인 2로 바꾸면 3 2 2 1이 된다. 다음 대치가 최대값 3을 찾고 다음 최대값인 2로 바꾸면 2 2 2 1이 된다. 서로 다른 종류의 수가 2가지 이하이므로 대치가 승리하였고 남은 수들 중 최소값은 1, 최대값은 2이다.
N개의 수들이 주어질 때, 게임의 승자와 현재 남은 수들 중 최소값과 최대값을 출력하는 프로그램을 작성하시오.
입력
첫 행에 수의 개수 N (1 ≤ N ≤ 100,000) 이 주어진다. 다음 행에 N개의 정수 Ai ( 1 ≤ Ai ≤ 100,000)가 공백으로 구분되어 주어진다.
출력
첫 행에 게임의 승자를 출력한다. 대치가 이긴 경우 MAX를 소치가 이긴 경우 MIN을 출력한다. 두 번째 행에 현재 남은 수들 중 최소값과 최대값을 공백으로 구분하여 출력한다.
예제1
입력
3
333
출력
MAX
33
예제2
입력
4
3121
출력
MAX
12
예제3
입력
7
2133541
출력
MAX
23
출처
COCI 2014/2015 contest4