#P18035. Up-Down Sequence

Up-Down Sequence

Up-Down Sequence

给定整数 NN,请构造一个 1,2,…,N1,2,\ldots,N 的排列 PP,满足:

在所有 1≤i<j<k≤N1\le i<j<k\le N 的下标三元组中,满足 Pi<Pj<PkP_i<P_j<P_k 的三元组数量,等于满足 Pi>Pj>PkP_i>P_j>P_k 的三元组数量。

若无解,输出 −1-1。若有多个答案,可以输出任意一个。

输入格式

第一行一个整数 TT。接下来 TT 行,每行一个整数 NN。

输出格式

每组测试输出一行。如果不存在满足条件的排列,输出 -1;否则输出 NN 个整数,表示构造的排列。

数据范围

1≤T≤5×1051\le T\le5\times10^5,3≤N≤5×1053\le N\le5\times10^5。同一输入文件中所有测试的 NN 之和不超过 5×1055\times10^5。所有输入均为整数。

样例说明

N=3N=3 时排列 (1,3,2)(1,3,2) 的递增、递减三元组数量均为 00;N=4N=4 时排列 (2,4,1,3)(2,4,1,3) 的两种数量也均为 00。

样例 1

输入:

2
3
4

输出:

1 3 2
2 4 1 3