F. Странная сортировка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть перестановка — массив $$$a = [a_1, a_2, \ldots, a_n]$$$ из различных целых чисел от $$$1$$$ до $$$n$$$. Длина перестановки $$$n$$$ нечётна.

Рассмотрим следующий алгоритм сортировки перестановки по возрастанию.

Вспомогательная процедура алгоритма, $$$f(i)$$$, принимает на вход индекс $$$i$$$ ($$$1 \le i \le n-1$$$) и делает следующее. Если $$$a_i > a_{i+1}$$$, значения $$$a_i$$$ и $$$a_{i+1}$$$ меняются местами. В противном случае перестановка остаётся без изменений.

Алгоритм состоит из итераций, пронумерованных последовательными целыми числами, начиная с $$$1$$$. На $$$i$$$-й итерации алгоритм делает следующее:

  • если $$$i$$$ нечётно, вызываются $$$f(1), f(3), \ldots, f(n - 2)$$$;
  • если $$$i$$$ чётно, вызываются $$$f(2), f(4), \ldots, f(n - 1)$$$.

Можно доказать, что после конечного числа итераций перестановка станет отсортирована по возрастанию.

Через сколько итераций это впервые произойдёт?

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

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

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

Вторая строка содержит $$$n$$$ различных целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — саму перестановку.

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

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

Для каждого набора входных данных выведите число итераций, после которого заданная перестановка впервые окажется отсортирована по возрастанию.

Если заданная перестановка уже отсортирована, выведите $$$0$$$.

Пример
Входные данные
3
3
3 2 1
7
4 5 7 1 3 2 6
5
1 2 3 4 5
Выходные данные
3
5
0
Примечание

В первом наборе входных данных перестановка будет меняться следующим образом:

  • после $$$1$$$-й итерации: $$$[2, 3, 1]$$$;
  • после $$$2$$$-й итерации: $$$[2, 1, 3]$$$;
  • после $$$3$$$-й итерации: $$$[1, 2, 3]$$$.

Во втором наборе входных данных перестановка будет меняться следующим образом:

  • после $$$1$$$-й итерации: $$$[4, 5, 1, 7, 2, 3, 6]$$$;
  • после $$$2$$$-й итерации: $$$[4, 1, 5, 2, 7, 3, 6]$$$;
  • после $$$3$$$-й итерации: $$$[1, 4, 2, 5, 3, 7, 6]$$$;
  • после $$$4$$$-й итерации: $$$[1, 2, 4, 3, 5, 6, 7]$$$;
  • после $$$5$$$-й итерации: $$$[1, 2, 3, 4, 5, 6, 7]$$$.

В третьем наборе входных данных перестановка уже отсортирована, поэтому ответ равен $$$0$$$.