**【样例说明】**
当 $n=1$ 时,答案显然是 $1$ 。
当 $n=2$ 时, 全排列包括 $(1,2)$ 和 $(2,1)$, 其中 $(2,1)$ 拥有最长的完美子序列, 也就是 $(2,1)$ 本身, $2$ 阶最大完美长度为 $2$,答案即为 $2+1$ 。
当 $n=3$ 时,全排列包括 $(1,2,3)$、$(1,3,2)$、$(2,1,3)$、$(2,3,1)$、$(3,1,2)$、$(3,2,1)$ 。其中 $(2,1)$ 和 $(3,1)$ 都是最长的完美子序列,$3$ 阶最大完美长度为 $2$。
序列 $(1,2,3)$ 和 $(1,3,2)$ 中没有长度为 $2$ 的完美子序列。
序列 $(2,1,3)$ 中有完美子序列 $(2,1)$,价值和为 $3$。
序列 $(2,3,1)$ 中有完美子序列 $(2,1)$ 和 $(3,1)$,价值和为 $7$。
序列 $(3,1,2)$ 中有完美子序列 $(3,1)$,价值和为 $4$。
序列 $(3,2,1)$ 中有完美子序列 $(2,1)$ 和 $(3,1)$,价值和为 $7$。
答案为 $3+7+4+7=21$ 。
**【评测用例规模与约定】**
对于 $10 \%$ 的评测用例,$n \leq 10$;
对于 $20 \%$ 的评测用例,$n \leq 20$;
对于 $30 \%$ 的评测用例,$T \leq 20, n \leq 1000$;
对于 $40 \%$ 的评测用例,$T \leq 20, n \leq 10^{5}$;
对于所有评测用例,$1 \leq T \leq 10^{5}, 1 \leq n \leq 10^{6}$。
蓝桥杯 2021 第二轮省赛 A 组 J 题。