AT_pakencamp_2025_day3_m Up-Down Sequence

$ (1,2,\dots,N) $ の順列 $ P $ であって、以下の条件を満たすものが存在するかどうか判定してください。存在する場合、一つ構築してください。 - 整数 $ 1 \le i < j < k \le N $ であって $ P_i < P_j < P_k $ を満たすものの個数と、整数 $ 1 \le i < j < k \le N $ であって $ P_i > P_j > P_k $ を満たすものの個数が等しい。 $ T $ 個のテストケースが与えられるので、それぞれについて問題を解いてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \text{test}_1 $ $ \text{test}_2 $ $ \vdots $ $ \text{test}_T $ ここで、 $ \text{test}_i $ は $ i $ 番目のテストケースを表し、以下のような形式で与えられる。 > $ N $

各テストケースについて、条件を満たす順列が存在しない場合は `-1` を出力して改行せよ。 存在する場合、条件を満たす順列 $ P $ を空白区切りで出力して改行せよ。 解が複数存在する場合は、そのうちどれを出力してもよい。

### Sample Explanation 1 一つ目のテストケースについて、順列 $ (1,3,2) $ は、単調増加でも単調減少でもありません。よって、条件を満たしています。 二つ目のテストケースについて、例えば順列 $ (2,4,1,3) $ を考えると、 $ (P_i,P_j,P_k) $ の値の組として考えられるものは、 $ (2,4,1),(2,4,3),(4,1,3),(2,1,3) $ がありますが、これらの三つ組はすべて単調増加でも単調減少でもありません。よって、条件を満たしています。 ### Constraints - $ 1 \le T \le 5 \times 10^5 $ - $ 3 \le N \le 5 \times 10^5 $ - テストケース中の $ N $ の合計は $ 5 \times 10^5 $ 以下である。 - 入力はすべて整数である。