#P12373. 「LAOI-12」命运。

    ID: 13593 远端评测题 1000ms 512MiB 尝试: 0 已通过: 0 难度: 2 上传者: 标签>洛谷原创Special JudgeO2优化构造洛谷比赛

「LAOI-12」命运。

题目背景

题目描述

给定正整数 nn,请你构造一个长度为 nn排列使得其所有区间极差之和为 i=1n1i2\sum\limits_{i=1}^{n-1}i^2

一个区间的极差定义为这个区间的最大值减最小值。

输入格式

本题有多组测试数据。

第一行输入一个正整数 TT,表示测试数据组数。

对于每组测试数据,一行一个正整数 nn,表示构造的排列长度。

输出格式

TT 行,对于每组数据输出对应的排列。

1
3
3 1 2

提示

样例解释

对于样例一中构造的序列,共有 66 个区间:

  1. [1,1][1,1],极差为 00
  2. [2,2][2,2],极差为 00
  3. [3,3][3,3],极差为 00
  4. [1,2][1,2],极差为 22
  5. [2,3][2,3],极差为 11
  6. [1,3][1,3],极差为 22

由于 2+1+2=5=i=131i22+1+2=5=\sum\limits_{i=1}^{3-1}i^2,故构造合法。

数据范围

本题采用捆绑测试。

子任务编号 n\sum n 分值
11 10\le10 55
22 103\le10^3 3535
33 106\le10^6 6060

对于 100%100\% 的数据,满足 1T1031\le T\le 10^32n,n1062\le n,\sum n \le10^6