Задача №113812. Доктор
Домагой смотрит на руку Мате, играя в очень упрощённую версию игры «Ханаби». Для простоты скажем, что Мате держит в руке N карт, пронумерованных числами 1, 2, ..., N в каком-то фиксированном порядке (каждое из чисел от 1 до N соответствует ровно одной карте). Как и в настоящей игре, Мате не может менять порядок карт.
Домагой указывает Мате на подотрезок последовательности карт, после чего Мате «разворачивает» этот отрезок карт.
При развороте отрезка карт меняются местами первая и последняя карты отрезка, вторая и предпоследняя и так далее. Как и все мы, Домагой — большой любитель неподвижных точек, то есть таких карт, числа на которых совпадают с номером позиции этих карт (считая слева направо со стороны Домагоя). Поэтому Домагой хочет максимизорать число неподвижных точек после поворота какого-то подотрезка.
Помогите Домагою найти такой подотрезок, после разворота которого число неподвижных точек будет максимальным.
В первой строке вводится единственное число N — число кард в руке Мате ( 1 ≤ N ≤ 5·10 5 ). Во второй строке вводятся N различных целых чисел от 1 до N — карты в руке Мате в том порядке, в котором Домагой видит их.
Выведите два числа A и B , числа на картах, являющихся началом и концом отрезка, который надо развернуть, чтобы максимизировать число неподвижных точек.
Программа, верно работающая на тестах, в которых N ≤ 500 , оценивается в 30 баллов. Программа, верно работающая на тестах, в которых N ≤ 5 000 , оценивается в 60 баллов.
4 3 2 1 4
3 1
2 1 2
1 1
7 3 6 5 7 4 1 2
6 1