Рекорды и антирекорды

Перестановкой размера $n$ называется последовательность $n$ целых чисел $a\_1, a\_2, \ldots, a\_n$, в которой все значения от $1$ до $n$ встречаются ровно по одному разу.

Последовательность $b\_1, b\_2, \dots, b\_l$ является подпоследовательностью последовательности $a\_1, a\_2, \dots, a\_n$, если $b$ можно получить из $a$ удалением некоторых элементов (то есть $l \le n$ и существуют $i\_1 < i\_2 < \ldots < i\_l$ такие что $a\_{i\_t} = b\_t$).

• Элемент последовательности $a\_i$ называется рекордом, если он строго больше всех предыдущих элементов (то есть $a\_j < a\_i$ для всех $1 \le j < i$).
• Элемент последовательности $a\_i$ называется антирекордом, если он строго меньше всех предыдущих элементов (то есть $a\_j > a\_i$ для всех $1 \le j < i$).

Дана перестановка $p\_1, p\_2, \dots, p\_n$ размера $n$. Требуется разделить её на две непустые подпоследовательности $q$ и $r$. Иными словами, каждый элемент $p$ должен попасть ровно в одну из подпоследовательностей. При этом требуется максимизировать сумму количества рекордов в $q$ и количества антирекордов в $r$.

Каждый тест состоит из нескольких наборов входных данных. В первой строке содержится единственное целое число $t$ ($1 \le t \le 100\\,000$) --- количество наборов входных данных. В следующих $2t$ строках следуют описания наборов входных данных.

В первой строке описания каждого набора входных данных содержится одно целое число $n$ --- размер перестановки ($2 \le n \le 200\\,000$).

Во второй строке описания каждого набора входных данных содержатся $n$ целых чисел $p\_1, p\_2, \dots, p\_n$ --- исходная перестановка. Гарантируется, что среди элементов $p$ каждое число от $1$ до $n$ встречается ровно по одному разу.

Сумма $n$ по всем наборам входных данных не превосходит $200\\,000$.

Для каждого набора входных данных выведите одно целое число --- максимальную возможную сумму количества рекордов в $q$ и антирекордов в $r$ в оптимальном разбиении.

Один из способов оптимальным образом разбить $p$ на $q$ и $r$ в первом наборе входных данных (рекорды в $q$ и антирекорды в $r$ обведены):

• $q = \boxed{1}\ \boxed{2}\ \boxed{3}\ \boxed{5}$
• $r = \boxed{4}$

Один из способов оптимальным образом разбить $p$ на $q$ и $r$ во втором наборе входных данных:

• $q = \boxed{3}\ \boxed{8}\ 4\ 1\ 2\ \boxed{9}$
• $r = \boxed{10}\ \boxed{7}\ \boxed{5}\ 6$