F. Поле не должно быть пустым
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана перестановка$$$^{\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$$$).

Входные данные

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — длина перестановки $$$p$$$.

Вторая строка каждого набора входных данных содержит $$$n$$$ различных целых чисел $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$) — элементы перестановки $$$p$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — максимальное значение $$$f(p)$$$ после выполнения операции ровно один раз.

Пример
Входные данные
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
Примечание

В первом наборе входных данных $$$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$$$.