쿠글리체 (크리스마스 장식)

크리스마스 시즌이 다가오고 있다. 일 년 중 가장 아름다운 시기다. 마린과 요시프는 크리스마스 쇼핑을 마치고 돌아와 트리를 장식하기 시작했다.

그들은 길쭉한 상자 안에 나란히 놓인 크리스마스 장식 $n$개를 샀고, $i$번째 장식의 색은 $a_i$이다. 상자는 양쪽이 모두 열려 있어서 왼쪽 끝과 오른쪽 끝 어디에서든 장식을 꺼낼 수 있다. 상자가 투명하여 마린과 요시프는 각 장식의 색을 볼 수 있다.

그림은 상자의 초기 상태를 보여 준다. 마린은 첫 번째 차례에 왼쪽 끝에서 색 $1$인 장식 하나를 꺼내거나, 오른쪽 끝에서 색 $3$인 장식 하나를 꺼낼 수 있다.

마린과 요시프는 번갈아 가며 진행하고, 마린이 먼저 시작한다. 차례인 사람은 상자의 왼쪽 끝이나 오른쪽 끝에서 장식을 하나 꺼내 트리에 단다. 그 색이 아직 나온 적이 없으면 그 사람이 점수를 얻는다. 마지막 장식이 꺼내지면 게임이 끝난다. 점수가 더 많은 사람이 이기므로 두 사람 모두 자기 점수를 최대화하려고 한다. 두 사람은 최선을 다해 플레이한다. 게임이 끝났을 때의 결과를 출력하라.

첫 번째 줄에 상자 안 장식의 개수를 나타내는 정수 $n$ ($1 \le n \le 3\,000$)이 주어진다.

두 번째 줄에는 장식의 색을 나타내는 정수 $a_i$ ($1 \le a_i \le n$) $n$개가 주어진다.

한 줄에 두 수를 :로 이어서 출력하라. 앞의 수는 마린의 점수, 뒤의 수는 요시프의 점수이다.

첫 번째 차례에 마린이 왼쪽 끝에서 색 $1$인 장식을 꺼내 1점을 얻는다. 요시프는 오른쪽 끝에서 색 $1$인 장식을 꺼내지만, 색 $1$은 이미 나왔으므로 점수를 얻지 못한다. 마린은 왼쪽 끝에서 색 $1$인 장식을 또 꺼내고 점수를 얻지 못한다. 요시프는 왼쪽 끝에서 색 $2$인 장식을 꺼낸다. 이 색이 처음 나온 것이므로 요시프가 1점을 얻는다. 마린은 왼쪽 끝에서 마지막 장식 (색 $1$)을 꺼내지만 점수를 얻지 못하고 게임이 끝난다. 마린은 1점, 요시프도 1점이므로 결과는 1:1이다.