数列を未整列にする 2

長さ $N$ の数列 $A$ が整列されているとは、すべての $1 \leq i < N$ に対して $A_i \leq A_{i+1}$ が成り立つことをいう。

$A$ の要素を並べ替えて得られる相異なる数列のうち、整列されていないものの個数を求めよ。

すべての位置の要素が等しい数列を同じものとみなす。要素の動かし方が異なっても、結果が同じなら $1$ 回だけ数える。例えば $A=(1,1,2)$ からは $(1,1,2)$、$(1,2,1)$、 が得られる。このうち整列されていないものは 個なので、答えは である。

入力は次の形式で与えられる。

$N$ $A_1\ A_2\ \cdots\ A_N$

条件を満たす相異なる数列の個数を出力せよ。

• $1 \leq N \leq 100\,000$.
• $-10^9\leq A_i\leq10^9$ ().