#960 Unsorting a Sequence 2

Statement

Statement language

A sequence $A$ of length $N$ is sorted if $A_i \leq A_{i+1}$ for every $1 \leq i < N$ .

Count the distinct sequences obtainable by rearranging the elements of $A$ that are not sorted.

Two sequences are equal when their elements agree at every position. Different ways of moving elements that produce the same sequence are counted only once. For example, $A=(1,1,2)$ produces $(1,1,2)$ , $(1,2,1)$ , and . Two of these are not sorted, so the answer is .

Input

The input is given in the following format.

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

Output

Print the number of distinct sequences satisfying the condition.

Constraints

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

Subtasks

#	Score	Constraints
1	3	$N\leq3$ .
2	27	At most two distinct values occur in $A$ .
3	10	All elements of $A$ are distinct.
4	26	$N \leq 1000$ .

Samples

Sample 1

Input

3
1 1 2

Output

2

Sample 2

Input

3
5 5 5

Output

0