Дан массив \(a\) длины \(n\) и целое число \(k\), вам нужно найти два любых числа \(l\) и \(r\) (\(l \leq r\)) таких, что:
- Для каждого \(x\) \((l \leq x \leq r)\), \(x\) содержится в \(a\) хотя бы \(k\) раз (т.е. \(k\) или более элементов массива равны \(x\)).
- Значение \(r-l\) максимально среди возможных.
Если не существует подходящих чисел, выведите -1.
Например, если \(a=[11, 11, 12, 13, 13, 14, 14]\) и \(k=2\), то:
- для \(l=12\), \(r=14\) первое условие не выполнено, так как \(12\) содержится менее \(k=2\) раз.
- для \(l=13\), \(r=14\) первое условие выполнено, так как \(13\) содержится хотя бы \(k=2\) раз в \(a\) и \(14\) содержится хотя бы \(k=2\) раз в \(a\).
- для \(l=11\), \(r=11\) первое условие выполнено, так как \(11\) содержится хотя бы \(k=2\) раз в \(a\).
Пара \(l\) и \(r\) для которой выполнено первое условие и \(r-l\) максимально — это пара \(l = 13\), \(r = 14\).
Выходные данные
Для каждого набора входных данных выведите \(2\) числа, \(l\) и \(r\) которые удовлетворяют условиям, или «-1» если таких не существует.
Если ответов может быть несколько, выведите любой.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
7 2
11 11 12 13 13 14 14
5 1
6 3 5 2 1
6 4
4 3 4 3 3 4
14 2
1 1 2 2 2 3 3 3 3 4 4 4 4 4
|
13 14
1 3
-1
1 4
|