跌宕起伏的排列

题目描述

排列指的是对于一个长度为n的整数序列，其中1~n之间的每个数都不重不漏的在序列中有且仅出现过一次，且不会有1~n之外的数出现。例如 1,2,3,4 和 4,3,2,1都是合法的4的排列，但是1,5,2,3不是，因为排列中出现了1~4之外的数5,且4没有在排列中出现。

Orange喜欢排列，但他不喜欢排列过于单调，而是应该跌宕起伏一点，他定义一个了最跌宕起伏的排列，当且仅当排列中所有相邻的数字之差的绝对值的和最大，请你求出这个值。

换句话说，你需要构造一个序列 $a$，最大化如下函数的值：

输入格式

输入包含 $T + 1$ 行，第一行为测试用例组的数量，接下来的每个测试用例包含1行，为一个整数 $n(n \leq 10^5)$，表示排列的大小，你需要求出 $f(n)$ 的最大值。

数据保证 $\sum n \leq 10^6$。

输出格式

共 $T$ 行，每行一个整数，表示 $f(n)$ 的最大值。

样例 #1

样例输入 #1

2
5
2

样例输出 #1

11
1

提示

对于第一组测试用例，可以构造出的一个排列为：$$4\quad1\quad5\quad2\quad3$$ 因此 $f(5) = |1 - 4| + |5 - 1| + |2 - 5| + |3 - 2| = 11$，可以证明这样构造是最优的。