먼저 열린 분류함

문제

한 우체국의 분류대에는 1번부터 N번까지 번호가 붙은 분류함이 있다. 오늘 도착한 편지는 모두 N통이며, 직원은 편지를 도착한 순서대로 한 통씩 확인한다. 각 편지에는 넣어야 할 분류함의 번호가 적혀 있다. 같은 분류함으로 가는 편지가 여러 통일 수 있고, 하루 동안 편지가 한 통도 들어가지 않는 분류함도 있을 수 있다. 편지 한 통은 적힌 번호의 분류함 한 곳에만 들어간다. 우체국은 작업을 마친 뒤 분류함 하나를 골라 안내판에 표시하려 한다. 먼저 편지가 가장 많이 들어 있는 분류함을 후보로 삼는다. 그런 분류함이 여러 개라면, 오늘 처음 편지를 받은 시점이 가장 빠른 분류함을 고른다. 처음 편지를 받은 시점이란 도착 순서에서 해당 분류함의 번호가 처음 등장한 위치다. 예를 들어 어떤 분류함의 번호가 두 번째, 다섯 번째, 여덟 번째 편지에 적혀 있었다면 그 분류함은 편지 세 통을 받았고 처음 편지를 받은 시점은 2다. 동점일 때 분류함 번호의 크기나 마지막 편지를 받은 시점은 사용하지 않는다. 또한 도착 순서에서 서로 다른 두 분류함이 같은 위치에 처음 등장할 수는 없다. 편지는 적어도 한 통 있으므로 최다 편지 수는 항상 양수이며, 비어 있는 분류함이 최종 선택되는 일도 없다. 이 규칙에 따라 선택되는 분류함은 항상 하나로 정해진다. 편지의 도착 순서에 따라 분류함 번호가 주어질 때, 안내판에 표시할 분류함 번호와 그 안에 들어 있는 편지 수를 구하는 프로그램을 작성한다. 편지의 순서는 입력에 나타난 순서 그대로이며, 선택을 위해 편지를 다시 정렬하거나 다른 분류함으로 옮기지는 않는다.

입력

첫째 줄에 정수 N이 주어진다.
둘째 줄에 각 편지의 분류함 번호를 나타내는 N개의 정수 A_1, A_2, ..., A_N이 도착 순서대로 주어진다.
1 ≤ N ≤ 100,000이며, 모든 i에 대해 1 ≤ A_i ≤ N이다.

출력

선택된 분류함의 번호와 그 분류함에 들어 있는 편지 수를 공백으로 구분하여 한 줄에 출력한다.

7
4 2 2 4 7 7 1

4 2

8
6 3 3 2 2 2 6 3

3 3

1
1

1 1

출처: Devin.KR 자체 제작