19096번 - Permutation 스페셜 저지다국어

Byteasar urgently needs two integer sequences for his research: an increasing one and a decreasing one. However, the only thing he has is a permutation $(p_1, p_2, \ldots, p_n)$ of the numbers in the range $[1, n]$. Can you help him partition this permutation into two such sequences?

Formally, we're looking for two subsequences $p_{r_1}, p_{r_2}, \ldots, p_{r_R}$ and $p_{m_1}, p_{m_2}, \ldots, p_{m_M}$ ($R, M \geq 0$) such that:

• $1 \leq r_1 < \ldots < r_R \leq n$ and $p_{r_1}<\ldots<p_{r_R}$,
• $1 \leq m_1 < \ldots < m_M \leq n$ and $p_{m_1}>\ldots>p_{m_M}$,
• $r_i \neq m_j$ for all $i,j$ ($1\leq i\leq R$, $1\leq j\leq M$),
• $R+M=n$.

The first line of the input contains a single integer $t$ ($1 \leq t \leq 50$) -- the number of testcases in the input file. The following lines describe the consecutive testcases.

A single testcase description consists of two lines. The first of them contains an integer $n$ ($1 \leq n \leq 100\,000$) -- the length of the permutation $(p_i)$. The following line contains $n$ integers $p_1, \ldots, p_n$ ($1 \leq p_i \leq n$ and $p_i \neq p_j$ for all $i \neq j$) -- the permutation itself.

For each testcase (in the order they appear in the input) you should output YES if the permutation can be partitioned into suitable subsequences or NO otherwise. If the partitioning is possible, you should output another two lines describing a sample solution. You should follow the format described below: $$R \; p_{r_1} \; p_{r_2} \; \ldots \; p_{r_R}$$ $$M \; p_{m_1} \; p_{m_2} \; \ldots \; p_{m_M}$$ In case there are many solutions, you can output any of them.