Назовем последовательность целых чисел хорошей k-d-последовательностью, если в нее можно добавить не более k чисел так, что после сортировки последовательность станет арифметической прогрессией с разностью d.
К вам в руки попала некая последовательность a, состоящая из n целых чисел. Вам требуется найти наидлиннейший непрерывный ее подотрезок, такой, что он является хорошей k-d-последовательностью.
Выходные данные
Выведите через пробел два целых числа l, r (1 ≤ l ≤ r ≤ n), которые обозначают, что последовательность al, al + 1, ..., ar — наидлиннейший подотрезок, являющийся хорошей k-d-последовательностью.
Если существует несколько оптимальных вариантов ответа, выведите ответ c наименьшим значением l.
Примечание
В первом тестовом примере ответом является отрезок, состоящий из чисел 2, 8, 6 — после добавления числа 4 и сортировки он превращается в последовательность 2, 4, 6, 8 — арифметическую прогрессию с разностью 2.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 1 2
4 3 2 8 6 2
|
3 5
|