こういうのは典型の1つでそれぞれの数字が何回足されるかということを考えるといいです。

まず最大値の数字は0回です。それ以外を考えていきましょう。

愚直に考えて、数える回数が分からないときは、確率で考えるといいです。

同じ数字もすべて区別して考えると、ある整数 $m$ に注目したとき、 $m$ 以上の数が $cnt _ {m}$ 個あるとき、自分がその先頭にいかないと数えられないので、確率は $\dfrac{1}{cnt _ {m}}$ になります。

なのである整数 $m$ は $\dfrac{n!}{cnt _ {m}}$ 回足されることになります。

よって、求める値は

$\displaystyle \sum _ {i = 1} ^ {n} a _ {i} \dfrac{n!}{cnt _ {a _ {i}}}$

$cnt _ {m}$ は小さいほうから見るなり、前計算するなり、データ構造使うなりで高速に求めることができます。

提出コード

まとめ

AtCoderやってるとこういうのには強くなるよね