수열 안 정렬하기 2

길이 $N$의 수열 $A$가 정렬되어 있다는 것은 모든 $1 \leq i < N$에 대해 $A_i \leq A_{i+1}$이 성립한다는 뜻이다.

$A$의 원소들을 재배열하여 만들 수 있는 서로 다른 수열 중, 정렬되어 있지 않은 수열의 개수를 구하라.

두 수열은 모든 위치의 원소가 같을 때 같은 수열이다. 원소를 옮기는 방법이 달라도 결과가 같으면 한 번만 센다. 예를 들어 $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$ ().