对于一个排列 A = (a₁, a₂, · · · , a_n)，定义价值 c_i 为 a₁ 至 a_i−1 中小于 a_i 的数的个数，即 b_i = |{a_j | j < i, a_j < a_i}|。定义 A 的价值为。

给定 n，求 1 至 n 的全排列中所有排列的价值之和。

3

9

1 至 3 构成的所有排列的价值如下:

(1, 2, 3) : 0 + 1 + 2 = 3 ；

(1, 3, 2) : 0 + 1 + 1 = 2 ；

(2, 1, 3) : 0 + 0 + 2 = 2 ；

(2, 3, 1) : 0 + 1 + 0 = 1 ；

(3, 1, 2) : 0 + 0 + 1 = 1 ；

(3, 2, 1) : 0 + 0 + 0 = 0 ；

故总和为 3 + 2 + 2 + 1 + 1 = 9。 

对于 40% 的评测用例，n ≤ 20 ；

对于 70% 的评测用例，n ≤ 5000 ；

对于所有评测用例，2 ≤ n ≤ 10⁶ 。