Егор — самый крутой житель своего города. Все знакомы с его подвигами и достижениями, но мало кто знает, что Егор жадный. Поэтому он решил установить на крышу своего замка солнечную панель, которая будет вырабатывать электричество за счет солнечного света.
Крыша замка состоит из $$$n$$$ фрагментов. Высота $$$i$$$-го фрагмента равна $$$h_i$$$. Солнечную панель можно поставить только на какой-то подотрезок фрагментов, при чём этот подотрезок должен быть отсортированной последовательностью. Более формально, пусть панель лежит на фрагментах с $$$l$$$-го по $$$r$$$-й $$$(1 \le l \le r \le n)$$$, тогда должно выполняться одно из двух:
Так как от размера панели зависит количество вырабатываемой энергии, то нужно, чтобы длина подотрезка была как можно больше. Помогите Егору найти такие $$$l$$$ и $$$r$$$ $$$(1 \le l \le r \le n)$$$, чтобы подотрезок с $$$l$$$ по $$$r$$$ содержал максимально возможное количество фраментов и был отсортированным.
В первой строке дано число $$$n$$$ $$$(1 \le n \le 10^6)$$$ — количество фрагментов крыши.
В следующей строке дано $$$n$$$ чисел $$$h_1,\ h_2,\ h_3,\ \ldots,\ h_n$$$ $$$(1 \le h_i \le 10^9)$$$ — высоты соответствующих фрагментов крыши.
Выведите два числа $$$l$$$ и $$$r$$$ $$$(1 \le l \le r \le n)$$$ — ответ на задачу. Если есть несколько вариантов ответа, то выведите любой.
Тесты к этой задаче состоят из нескольких групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов всех необходимых групп.
| Группа | Баллы | Ограничения | Необх. группы |
| 0 | 0 | Тесты из условия. | – |
| 1 | 5 | $$$n = 2$$$ | – |
| 2 | 19 | $$$n \le 100$$$ | 0, 1 |
| 3 | 25 | $$$n \le 1000$$$ | 0, 1, 2 |
| 4 | 51 | – | 0, 1, 2, 3 |
5 2 9 4 3 5
2 4
2 1000000000 999999999
1 2
1 1
1 1
В первом тесте подотрезк $$$h_2, h_3, h_4$$$ является отсортированной последовательностью $$$9, 4, 3$$$. Не трудно убедиться, что ответ не может быть больше.
Во втором и третьем тесте, подходит подотрезок, состоящий из всех фрагментов.
| Название |
|---|


