Uma permutação de tamanho $n$ é uma sequência de $n$ números inteiros $a_1,a_2,\ldots,a_n$ na qual cada valor de $1$ a $n$ aparece exatamente uma vez.
Uma sequência $b_1,b_2,\ldots,b_l$ é uma subsequência de $a_1,a_2,\ldots,a_n$ se $b$ pode ser obtida removendo alguns elementos de $a$ (isto é, $l\le n$ e existem $i_1<i_2<\cdots<i_l$ tais que $a_{i_t}=b_t$).
- Um elemento $a_i$ de uma sequência é chamado de recorde se for estritamente maior que todos os elementos anteriores (isto é, $a_j<a_i$ para todo $1\le j<i$).
- Um elemento $a_i$ de uma sequência é chamado de antirrecorde se for estritamente menor que todos os elementos anteriores (isto é, $a_j>a_i$ para todo $1\le j<i$).
É dada uma permutação $p_1,p_2,\ldots,p_n$ de tamanho $n$. É necessário dividi-la em duas subsequências não vazias $q$ e $r$. Em outras palavras, cada elemento de $p$ deve pertencer a exatamente uma das subsequências. Deve-se maximizar a soma do número de recordes em $q$ com o número de antirrecordes em $r$.
Entrada
Cada teste contém vários casos de teste. A primeira linha contém um único inteiro $t$ ($1\le t\le100\,000$), o número de casos de teste. As próximas $2t$ linhas contêm suas descrições.
A primeira linha da descrição de cada caso de teste contém um inteiro $n$, o tamanho da permutação ($2\le n\le200\,000$).
A segunda linha contém $n$ inteiros $p_1,p_2,\ldots,p_n$, a permutação original. É garantido que cada número de $1$ a $n$ aparece exatamente uma vez entre os elementos de $p$.
A soma de $n$ em todos os casos de teste não excede $200\,000$.
Saída
Para cada caso de teste, imprima um inteiro: a maior soma possível do número de recordes em $q$ com o número de antirrecordes em $r$ em uma divisão ótima.
Subtarefas
Denote por $N$ a soma dos valores de $n$ em todos os casos de teste de um teste.
| Subtarefa | Pontos | Restrições sobre $n,N$ | Restrições adicionais | Subtarefas necessárias | Informações sobre a avaliação |
|---|---|---|---|---|---|
| $1$ | $21$ | $n\le16$ | $t\le120$ | Exemplos | Primeiro erro |
| $2$ | $22$ | $n\le200$, $N\le2000$ | Exemplos, $1$ | Primeiro erro | |
| $3$ | $14$ | $N\le2\,000$ | Exemplos, $1$–$2$ | Primeiro erro | |
| $4$ | $10$ | $N\le10\,000$ | Exemplos, $1$–$3$ | Primeiro erro | |
| $5$ | $13$ | $N\le200\,000$ | O comprimento da maior subsequência decrescente de $p$ não excede $2$ | Primeiro erro | |
| $6$ | $20$ | $N\le200\,000$ | Exemplos, $1$–$5$ | Primeiro erro |
Exemplos
Entrada 1
4 5 4 1 2 3 5 10 3 8 10 4 1 2 7 9 5 6 3 1 2 3 6 4 2 5 1 6 3
Saída 1
5 6 3 5
Observação
Uma maneira de dividir $p$ em $q$ e $r$ de forma ótima no primeiro caso de teste (os recordes em $q$ e os antirrecordes em $r$ estão destacados em caixas):
- $q=\boxed{1}\ \boxed{2}\ \boxed{3}\ \boxed{5}$
- $r=\boxed{4}$
Uma maneira de dividir $p$ em $q$ e $r$ de forma ótima no segundo caso de teste:
- $q=\boxed{3}\ \boxed{8}\ 4\ 1\ 2\ \boxed{9}$
- $r=\boxed{10}\ \boxed{7}\ \boxed{5}\ 6$