616D.md (1421B)
1 Source: https://codeforces.com/problemset/problem/616/D 2 3 D. Longest k-Good Segment 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 The array *a* with *n* integers is given. Let's call the sequence of one or more consecutive elements in *a* segment. Also let's call the segment k-good if it contains no more than *k* different values. 22 23 Find any longest k-good segment. 24 25 As the input/output can reach huge size it is recommended to use fast input/output methods: for example, prefer to use scanf/printf instead of cin/cout in C++, prefer to use BufferedReader/PrintWriter instead of Scanner/System.out in Java. 26 27 Input 28 29 The first line contains two integers *n*, *k* (1 ≤ *k* ≤ *n* ≤ 5·105) — the number of elements in *a* and the parameter *k*. 30 31 The second line contains *n* integers *a**i* (0 ≤ *a**i* ≤ 106) — the elements of the array *a*. 32 33 Output 34 35 Print two integers *l*, *r* (1 ≤ *l* ≤ *r* ≤ *n*) — the index of the left and the index of the right ends of some k-good longest segment. If there are several longest segments you can print any of them. The elements in *a* are numbered from 1 to *n* from left to right. 36 37 Examples 38 39 Input 40 41 ``` 42 5 5 43 1 2 3 4 5 44 ``` 45 46 Output 47 48 ``` 49 1 5 50 ``` 51 52 Input 53 54 ``` 55 9 3 56 6 5 1 2 3 2 1 4 5 57 ``` 58 59 Output 60 61 ``` 62 3 7 63 ``` 64 65 Input 66 67 ``` 68 3 1 69 1 2 3 70 ``` 71 72 Output 73 74 ``` 75 1 1 76 ```