Вам дана перестановка \(p\) длины \(n\). Вы хотите минимизировать количество подотрезков \(p\), которые являются перестановками. Для этого вы должны выполнить следующую операцию ровно один раз:
- Выбрать целые числа \(i\), \(j\), где \(1 \le i, j \le n\), затем
- Поменять местами \(p_i\) и \(p_j\).
Например, если \(p = [5, 1, 4, 2, 3]\) и мы выбираем \(i = 2\), \(j = 3\), то итоговый массив будет равен \([5, 4, 1, 2, 3]\). Если вместо этого мы выберем \(i = j = 5\), то итоговый массив будет \([5, 1, 4, 2, 3]\).
При каком выборе \(i\) и \(j\) количество подотрезков, являющихся перестановками, будет минимальным?
Перестановка длины \(n\) — это массив, состоящий из \(n\) различных целых чисел от \(1\) до \(n\) в произвольном порядке. Например, \([2,3,1,5,4]\) является перестановкой, но \([1,2,2]\) не является перестановкой (\(2\) дважды встречается в массиве), и \([1,3,4]\) также не является перестановкой (\(n=3\), но в массиве есть \(4\)).
Массив \(a\) является подотрезком массива \(b\), если \(a\) можно получить из \(b\) путем удаления нескольких (возможно, нуля или всех) элементов из начала и нескольких (возможно, нуля или всех) элементов из конца.
Выходные данные
Для каждого набора входных данных выведите два целых числа \(i\) и \(j\) (\(1 \le i, j \le n\)) — индексы, которые нужно поменять местами в \(p\).
Если существует несколько решений, выведите любое из них.
Примечание
В первом примере после замены возможны четыре массива:
- Если мы поменяем местами \(p_1\) и \(p_2\), то получим массив \([2, 1, 3]\), который имеет 3 подотрезка, которые являются перестановками (\([1]\), \([2, 1]\), \([2, 1, 3]\)).
- Если поменять местами \(p_1\) и \(p_3\), то получим массив \([3, 2, 1]\), который имеет 3 подотрезка, которые являются перестановками (\([1]\), \([2, 1]\), \([3, 2, 1]\)).
- Если поменять местами \(p_2\) и \(p_3\), мы получим массив \([1, 3, 2]\), который имеет 2 подотрезка, которые являются перестановками (\([1]\), \([1, 3, 2]\)).
- Если поменять любой элемент местами с самим собой, мы получим массив \([1, 2, 3]\), который имеет 3 подотрезка, которые являются перестановками (\([1]\), \([1, 2]\), \([1, 2, 3]\)).
Поэтому лучше всего поменять местами элементы на позициях
\(2\) и
\(3\).
В третьем примере, после того, как мы поменяем местами элементы на позициях \(2\) и \(5\), итоговый массив будет равняться \([1, 4, 2, 5, 3]\). Единственными подотрезками, которые являются перестановками, будут \([1]\) и \([1, 4, 2, 5, 3]\). Мы можем показать, что это минимально возможное количество.