택배 상자의 목적지 묶음

문제

택배 작업대에는 상자 N개가 왼쪽에서 오른쪽으로 한 줄로 놓여 있다. 각 상자에는 배송 구역을 나타내는 양의 정수 하나가 붙어 있다. 작업자는 상자를 놓인 순서대로 확인하며, 같은 구역으로 가는 상자가 연속해서 놓인 부분을 하나의 묶음으로 기록하려고 한다. 상자의 위치를 바꾸거나 다른 위치의 상자를 가져와 합칠 수는 없다. 하나의 묶음은 배송 구역 번호가 모두 같은 연속한 상자들로 이루어진다. 묶음의 바로 앞이나 바로 뒤에 같은 구역 번호의 상자가 있으면 그 상자까지 반드시 같은 묶음에 포함해야 한다. 따라서 같은 번호가 이어지는 부분을 임의로 여러 묶음으로 나누는 것은 허용되지 않는다. 반대로 번호가 다른 두 상자를 하나의 묶음에 넣을 수도 없다. 예를 들어 구역 번호가 4, 4, 9, 4 순서라면 처음 두 상자가 첫 번째 묶음이고, 세 번째 상자와 네 번째 상자가 각각 다음 묶음이 된다. 첫 번째 묶음과 마지막 묶음의 구역 번호가 같더라도 그 사이에 다른 구역의 상자가 있으므로 서로 합치지 않는다. 모든 상자의 구역 번호가 같으면 묶음은 하나이며, 이웃한 상자의 구역 번호가 모두 다르면 각 상자가 하나의 묶음이 된다. 상자는 정확히 하나의 묶음에 속해야 하며, 기록에는 원래 줄에서 나타난 묶음의 순서를 유지한다. 구역 번호의 크기에 따라 묶음을 정렬하지 않는다. 작업 기록을 만들기 위해 전체 묶음 수와 각 묶음의 배송 구역 번호 및 상자 수를 구하는 프로그램을 작성한다.

입력

첫째 줄에 상자 수를 나타내는 정수 N이 주어진다. 1 ≤ N ≤ 50,000이다.
둘째 줄에 왼쪽부터 차례대로 각 상자의 배송 구역 번호 A_1, A_2, …, A_N이 공백으로 구분되어 주어진다. 모든 A_i는 정수이며 1 ≤ A_i ≤ 1,000이다.

출력

첫째 줄에 묶음 수 K를 출력한다. 다음 K개 줄에 각 묶음의 배송 구역 번호와 상자 수를 공백으로 구분하여 출력한다. 묶음은 원래 줄에서 왼쪽부터 나타나는 순서로 출력한다. N이 1 이상이므로 묶음이 없는 경우는 없다.

8
3 3 8 8 8 3 5 5

4
3 2
8 3
3 1
5 2

1
17

1
17 1

5
6 6 6 6 6

1
6 5

출처: Devin.KR 자체 제작