C. Солнечная панель
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Егор — самый крутой житель своего города. Все знакомы с его подвигами и достижениями, но мало кто знает, что Егор жадный. Поэтому он решил установить на крышу своего замка солнечную панель, которая будет вырабатывать электричество за счет солнечного света.

Крыша замка состоит из $$$n$$$ фрагментов. Высота $$$i$$$-го фрагмента равна $$$h_i$$$. Солнечную панель можно поставить только на какой-то подотрезок фрагментов, при чём этот подотрезок должен быть отсортированной последовательностью. Более формально, пусть панель лежит на фрагментах с $$$l$$$-го по $$$r$$$-й $$$(1 \le l \le r \le n)$$$, тогда должно выполняться одно из двух:

  • Либо $$$h_l \le h_{l+1} \le h_{l+2} \le \ldots \le h_r$$$.
  • Либо $$$h_l \ge h_{l+1} \ge h_{l+2} \ge \ldots \ge h_r$$$.

Так как от размера панели зависит количество вырабатываемой энергии, то нужно, чтобы длина подотрезка была как можно больше. Помогите Егору найти такие $$$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)$$$ — ответ на задачу. Если есть несколько вариантов ответа, то выведите любой.

Система оценки

Тесты к этой задаче состоят из нескольких групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов всех необходимых групп.

ГруппаБаллыОграниченияНеобх. группы
00Тесты из условия.–
15$$$n = 2$$$–
219$$$n \le 100$$$0, 1
325$$$n \le 1000$$$0, 1, 2
451–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$$$. Не трудно убедиться, что ответ не может быть больше.

Во втором и третьем тесте, подходит подотрезок, состоящий из всех фрагментов.