Playlist Display Intervals

Time limit1sMemory limit128 MB

Summary
Given a sequence of distinct requested songs, choose a length-K window covering each request to minimize the total number of distinct songs ever shown across all windows.
Level

Medium7 of 10

Topics
Greedy, Intervals, Simulation
Solved
No attempts yet

Problem

Igor has a very large music collection on his computer. The songs are numbered from 1 to N. The screen cannot show the whole collection at once, so when song S is playing, the screen shows exactly K consecutive songs and that block must include S.

When a song appears on the screen for the first time, the program must open its file and read metadata such as the artist and title. After that metadata is stored in memory, the same song can appear again without opening the file again.

You are given the songs Igor will listen to, in order. For each requested song, choose the consecutive block shown while it is playing. The number of distinct song files opened over the whole playlist must be as small as possible.

There may be more than one optimal answer.

Input

The first line contains two integers N and K: the number of songs and the number of songs shown on the screen.

The second line contains an integer M, the number of songs Igor will listen to.

Each of the next M lines contains one requested song number, in playback order. Every song number is between 1 and N, and no song number appears more than once.

Constraints:

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

Output

Print M+1 lines.

On the first line, print the minimum possible number of distinct song files that must be opened.

Then print M lines, one for each requested song S in input order. On each line print two integers A and B, meaning that songs A through B are shown while S is playing. Each line must satisfy:

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

Examples3

  1. Example 1

    Input
    10 3
5
4
5
8
7
6
    Expected output
    5
4 6
4 6
6 8
5 7
4 6

  2. Example 2

    Input
    15 4
6
6
14
11
3
8
5
    Expected output
    10
3 6
11 14
11 14
3 6
5 8
3 6

  3. Example 3

    Input
    1000 301
3
300
500
700
    Expected output
    401
300 600
300 600
400 700