У Дореми \(n\) ведерок с краской, они могут быть представленны в виде массива \(a\) длины \(n\). Ведерко \(i\) содержит краску цвета \(a_i\).
Пусть \(c(l,r)\) — количество различных цветов в подмассиве \([a_l,a_{l+1},\ldots,a_r]\). Выберите \(2\) целых числа \(l\) и \(r\) такие, что \(l \leq r\), а значение \(r-l-c(l,r)\) — максимально возможно.
Выходные данные
Для каждого набора входных данных выведите \(l\) и \(r\) такие, что \(l \leq r\), а значение \(r-l-c(l,r)\) — максимально возможно.
Если существуют несколько решений, выведите любое из них.
Примечание
В первом примере \(a=[1,3,2,2,4]\).
- Если \(l=1\) и \(r=3\), то \(c(l,r)=3\) (\(3\) различных элементов среди \([1,3,2]\)).
- Если \(l=2\) и \(r=4\), то \(c(l,r)=2\) (\(2\) различных элементов среди \([3,2,2]\)).
Можно показать, что выбор \(l=2\) и \(r=4\) максимизирует значение \(r-l-c(l,r)\), равное \(0\).
Во втором примере \(a=[1,2,3,4,5]\).
- Если \(l=1\) и \(r=5\), то \(c(l,r)=5\) (\(5\) различных элементов среди \([1,2,3,4,5]\)).
- Если \(l=3\) и \(r=3\), то \(c(l,r)=1\) (\(1\) различных элементов среди \([3]\)).
Можно показать, что выбор \(l=1\) и \(r=5\) максимизирует значение \(r-l-c(l,r)\), равное \(-1\). Выбор \(l=3\) и \(r=3\) также подходит.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
5
1 3 2 2 4
5
1 2 3 4 5
4
2 1 2 1
3
2 3 3
2
2 2
1
1
9
9 8 5 2 1 1 2 3 3
|
2 4
1 5
1 4
2 3
1 2
1 1
3 9
|