Ribbons
Output: Standard Output (stdout)
Memory limit: 128 megabytes
Time limit: 2.0 seconds
Arlene has acquired a very long and colourful ribbon that consists of N segments, the i-th of which has a colour v_i that is represented by an integer. While the whole ribbon is certainly a sight to behold, it is too long to wear so Arlene would like to cut out a smaller section of the ribbon that is at most M segments long. Arlene is concerned that having too many unique colours on her ribbon could bedazzle passersby and result in traffic accidents, so she wants to make sure that the section she cuts out to wear has at most K distinct colours.
Arlene wants to find out the length of the longest possible ribbon that she could cut, which needs to consist of at most M segments that are contiguous, and have at most K distinct colours. She would also like to know the number of different ribbons that she could cut of this length. Two ribbon sections are considered different if they include different segments. Arlene has asked for your help to write a program to calculate this for her.
Input
The first line contains three space separated integers N, M, K
The second line contains N space separated integers v_1, \dots, v_N
Output
On a single line output two integers, the length of the longest such ribbon section and the number of possible ribbon sections with this length.
Constraints
- 1 \le M, K \le N \le 100,000
- 1 \le v_i \le 10^9
Subtasks
- Subtask 1 (21%): K = 1
- Subtask 2 (13%): N \le 100
- Subtask 3 (16%): N \le 1,000
- Subtask 4 (22%): v_i \le 25 for all 1 \le i \le N
- Subtask 5 (28%): No further constraints.
Sample Explanations
Sample 1
In this sample the original ribbon is 8 segments long and Arlene wants to cut out a ribbon that is at most 6 sections long and has at most 2 distinct colours. The longest possible section of ribbon that she could cut is segments 5 through 7 and there are no other sections of ribbon with length 3 (or longer) that satisfy the two constraints.
Sample 2
In this sample the longest possible sections are (2, 3), (4, 5), (6, 7).
-
Sample Input 1
8 6 2 3 2 1 3 2 1 2 4
Sample Output 1
3 1
-
Sample Input 2
10 6 1 1 5 5 3 3 5 5 3 4 1
Sample Output 2
2 3
-
Sample Input 3
7 4 3 1 2 1 2 3 3 4
Sample Output 3
4 4