# Max Sum Array
Mấy bài công thức thì ta nên nháp nháp tìm cách tách công thức, biến đổi công thức về dạng dễ hơn các thứ.
Xét với 1 loại số có m số, gọi vị trí xuất hiện trong dãy là $t_1, t_2, ..., t_m$.
Ta thấy với $t_i$ thì nó được cộng vào công thức $i - 1$ lần, và trừ vào công thức $m - i$ lần
=> $res$ += $t_i * (i - 1 - m + i)$ = $t_i * (i * 2 - m - 1)$.

Ví dụ với dãy 4 số $t_1, t_2, t_3, t_4$ thì
$res$ += $t_1 * -3 + t_2 * -1 + t_3 * 1 + t_4 * 3$

Với dãy 5 số $t_1, t_2, t_3, t_4, t_5$ thì
$res$ += $t_1 * -4 + t_2 * -2 + t_3 * 0 + t_4 * 2 + t_5 * 4$

Gọi $f[i]$ là số loại có số * với $i$.
Dễ thấy mấy hệ số là $1$ dãy liên tiếp cách đều $2$ nên ta có thể dùng tăng đầu giảm cuối, cộng dồn để tính nhanh mảng $f$.

Giờ ta cần đáp án MAX, nên những thằng có hệ số càng cao ta sẽ càng để lên đầu dãy.

Xét với $f[i]$ và còn $sum$ vị trí trống (từ $1$ đến $sum$). Ta sẽ đặt luôn $f[i]$ thằng vào cuối dãy. Khi đó:
$res$ += $i * (sum + sum-1 + sum-2 + ... + sum-f[i]+1)$
Ta có $f[i]$! cách xếp $f[i]$ thằng vào cuối nên $socach$ *= $f[i]!$

Cách này có thêm mấy vấn đề:
- $f[i]$, $i$ chạy từ -$1e6$ -> $1e6$ nên ta cần cộng thêm để không chạy lỗi.
- vì phải dùng MOD nên phải cẩn thận khi tính công thức trên.