Вам дана перестановка\(^{\dagger}\) \(p\) длины \(n\).
Мы называем индекс \(x\) хорошим, если для всех \(y < x\) выполняется условие \(p_y < p_x\), и для всех \(y > x\) выполняется условие \(p_y > p_x\). Обозначим \(f(p)\) как количество хороших индексов в \(p\).
Вы можете выполнить следующую операцию: выберите \(2\) различных индекса \(i\) и \(j\) и поменяйте местами элементы \(p_i\) и \(p_j\).
Найдите максимальное значение \(f(p)\) после применения вышеупомянутой операции ровно один раз.
\(^{\dagger}\)Перестановкой длины \(n\) является массив, состоящий из \(n\) различных целых чисел от \(1\) до \(n\) в произвольном порядке. Например, \([2,3,1,5,4]\) — перестановка, но \([1,2,2]\) не перестановка (\(2\) встречается в массиве дважды) и \([1,3,4]\) тоже не перестановка (\(n=3\), но в массиве встречается \(4\)).
Выходные данные
Для каждого набора входных данных выведите одно целое число — максимальное значение \(f(p)\) после выполнения операции ровно один раз.
Примечание
В первом наборе входных данных \(p = [1,2,3,4,5]\) и \(f(p)=5\), что уже является максимально возможным. Но операцию нужно выполнить в любом случае. Мы можем получить \(f(p)=3\), выбрав \(i=1\) и \(j=2\), после чего \(p = [2,1,3,4,5]\).
Во втором наборе входных данных мы можем преобразовать \(p\) в \([1,2,3,4,5]\), выбрав \(i=1\) и \(j=2\). Таким образом, \(f(p)=5\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
5
1 2 3 4 5
5
2 1 3 4 5
7
2 1 5 3 7 6 4
6
2 3 5 4 1 6
7
7 6 5 4 3 2 1
|
3
5
2
3
2
|