재생 목록 표시 구간

시간 제한1초메모리 제한128 MB

요약
중복 없이 요청되는 곡들에 대해 각 곡을 포함하는 길이 K 구간을 골라 전체적으로 열리는 파일(곡) 개수를 최소화하는 문제입니다.
난이도

보통10점 중 7점

유형
그리디, 구간, 시뮬레이션
정답자
아직 제출이 없습니다

문제

이고르는 컴퓨터에 1번부터 N번까지 번호가 붙은 노래를 아주 많이 가지고 있다. 화면에는 모든 노래를 한 번에 보여 줄 수 없어서, 어떤 노래 S를 재생할 때는 S를 포함하는 연속한 K개의 노래만 화면에 표시된다.

어떤 노래가 처음 화면에 나타나면 프로그램은 그 노래 파일을 열어 가수와 제목 같은 메타데이터를 읽어야 한다. 한 번 읽은 메타데이터는 메모리에 저장되므로, 같은 노래가 나중에 다시 화면에 나타나도 파일을 다시 열 필요가 없다.

이고르가 들을 노래들이 순서대로 주어진다. 각 노래가 재생될 때 화면에 표시할 연속 구간을 하나씩 정하라. 모든 재생이 끝날 때까지 파일을 열어야 하는 서로 다른 노래 수가 최소가 되어야 한다.

최적해는 여러 개일 수 있다.

입력

첫째 줄에 두 정수 N과 K가 주어진다. N은 전체 노래 수, K는 화면에 표시되는 노래 수이다.

둘째 줄에 이고르가 들을 노래 수 M이 주어진다.

다음 M개의 줄에는 재생할 노래 번호가 순서대로 하나씩 주어진다. 모든 노래 번호는 1 이상 N 이하이고, 같은 노래는 두 번 이상 주어지지 않는다.

제한은 다음과 같다.

  • 1 <= K < N < 1,000,000,000
  • 1 <= M <= 300,000

출력

총 M+1개의 줄을 출력한다.

첫째 줄에는 파일을 열어야 하는 서로 다른 노래 수의 최솟값을 출력한다.

그다음 M개의 줄에는 입력으로 주어진 각 노래 S에 대해 두 정수 A와 B를 출력한다. 이는 S가 재생될 때 화면에 A번부터 B번까지의 노래가 표시된다는 뜻이다. 각 줄은 다음 조건을 만족해야 한다.

  • 1 <= A <= S <= B <= N
  • B - A + 1 = K

예제3

  1. 예제 1

    입력
    10 3
5
4
5
8
7
6
    예상 출력
    5
4 6
4 6
6 8
5 7
4 6

  2. 예제 2

    입력
    15 4
6
6
14
11
3
8
5
    예상 출력
    10
3 6
11 14
11 14
3 6
5 8
3 6

  3. 예제 3

    입력
    1000 301
3
300
500
700
    예상 출력
    401
300 600
300 600
400 700