Logan is cleaning his apartment. In particular, he must sort his old favorite sequence, ${P}$, of $N$ positive integers in nondecreasing order. He's tired from a long day, so he invented an easy way (in his opinion) to do this job. His algorithm can be described by the following pseudocode:

while isNotSorted(P) do {   
    WaitOneMinute();
    RandomShuffle(P)
}

Can you determine the expected number of minutes that Logan will spend waiting for ${P}$ to be sorted?

Input Format

The first line contains a single integer, $N$, denoting the size of permutation ${P}$. 

The second line contains $N$ space-separated integers describing the respective elements in the sequence's current order, $P_0,P_1,\ldots,P_{N-1}$.

Constraints

$2\leq N\leq18$
$1\leq P_i\leq100$

Output Format

Print the expected number of minutes Logan must wait for ${P}$ to be sorted, correct to  ${6}$ decimal places.

Sample Input
2
5 2

Sample Output
2.000000

Explanation

There are two permutations possible after a random shuffle, and each of them has probability $0.5$. The probability to get the sequence sorted after the first minute is $0.5$. The probability that ${P}$ will be sorted after the second minute is ${0.25}$, the probability ${P}$ will be sorted after the third minute is ${0.125}$, and so on. So, the answer is equal to the following sum: $\sum_{i=1}^{\infty}i\times2^{-i}=2$

Difficulty: MEDIUM
Tags: Probability

Starter code:

Solutions:
from math import factorial
N = int(input())
a = list(map(int, input().split()))
if a == sorted(a):
	print(0)
else:
	m = {}
	for i in a:
		if i in m:
			m[i] += 1
		else:
			m[i] = 1
	num = 1
	for i in m:
		num *= factorial(m[i])
	den = factorial(N)
	print('%0.6f' % (den / num))


import sys

def factorial(n):
	return 1 if n == 0 else n * factorial(n - 1)
n = int(input().strip())
P = [int(_) for _ in input().strip().split(' ')]
if sorted(P) == P:
	t = 0
else:
	counter = [0] * 101
	for x in P:
		counter[x] += 1
	base = 1
	for i in counter:
		base *= factorial(i)
	t = factorial(n) / base
print('{:.6f}'.format(t))


from collections import Counter
from math import factorial

def is_sorted(a):
	for i in range(1, len(a)):
		if a[i - 1] > a[i]:
			return False
	return True
n = int(input())
p = list(map(int, input().split()))
if is_sorted(p):
	print('0.000000')
else:
	cnt = Counter(p)
	perm_num = factorial(n)
	for (x, c) in cnt.items():
		perm_num //= factorial(c)
	print(perm_num, '.000000', sep='')


from itertools import permutations
F = [1]
for i in range(1, 19):
	F.append(F[-1] * i)

def solve(P):
	Ps = tuple(sorted(P))
	if P == Ps:
		return 0
	count = {}
	for p in P:
		count[p] = count.get(p, 0) + 1
	countSorted = 1
	for p in count:
		countSorted *= F[count[p]]
	return F[len(P)] / countSorted
N = int(input())
P = tuple(map(int, input().split()))
print('{0:.6f}'.format(solve(P)))


from math import factorial
N = int(input())
P = list(map(int, input().split()))

def solve(P):
	sorted_P = sorted(P)
	if P == sorted_P:
		return 0
	else:
		count_P = {}
		for number in sorted_P:
			if number not in count_P:
				count_P[number] = 1
			else:
				count_P[number] += 1
		numerator = factorial(len(P))
		denominator = 1
		for number in count_P:
			if count_P[number] > 1:
				denominator *= factorial(count_P[number])
		return numerator / denominator
print('%.6f' % solve(P))


import math
n = int(input())
l = []
default_v = 0
dic = dict.fromkeys([x for x in range(1, 101)], default_v)
for x in input().split():
	x = int(x)
	dic[x] += 1
	l.append(x)
l2 = sorted(l)
if l == l2:
	print('0.000000')
else:
	l = set(l)
	ans = math.factorial(n)
	for x in l:
		ans = int(ans / math.factorial(dic[x]))
	final = str(ans) + '.000000'
	print(final)


import math
N = int(input())
arr = map(lambda x: int(x), input().split())
dups = {}
st = 0
sortd = True
for num in arr:
	if num < st:
		sortd = False
	st = num
	if dups.get(num) is None:
		dups[num] = 1
	else:
		dups[num] += 1
if sortd:
	print('{:.6f}'.format(0))
else:
	rep = 1
	for (_, v) in dups.items():
		rep *= math.factorial(v)
	res = math.factorial(N) / rep
	print('{:.6f}'.format(res))


from collections import defaultdict
N = int(input())
P = [int(x) for x in input().strip().split()]
SP = sorted(P)
if P == SP:
	print(0)
else:
	facs = [1]
	for i in range(1, N + 1):
		facs.append(facs[-1] * i)
	cnt = defaultdict(int)
	for x in P:
		cnt[x] += 1
	acc = facs[N]
	for (k, v) in cnt.items():
		acc /= facs[v]
	print('%.6f' % acc)


import sys

def fact(n):
	if n < 2:
		return 1
	else:
		return n * fact(n - 1)
n = int(input())
l = sys.stdin.readline().split(' ')
trie = True
k = 0
dejaVu = {}
for i in l:
	if i in dejaVu:
		dejaVu[i] += 1
	else:
		dejaVu[i] = 1
while trie and k < n - 1:
	if int(l[0]) > int(l[1]):
		trie = False
	l = l[1:]
	k += 1
if trie:
	print('0.000000')
else:
	listeFact = [fact(dejaVu[i]) for i in dejaVu.keys()]
	denom = 1
	for i in listeFact:
		denom = denom * i
	result = fact(n) / denom
	result = round(result, 6)
	result2 = str(round(result - int(result), 6))
	while len(result2) < 8:
		result2 = result2 + '0'
		result = str(result) + '0'
	print(result)


import sys
import math

def split_sorted_list_in_clusters(l):
	clusters = []
	cur_cluster_start = 0
	prev_val = None
	for (i, val) in enumerate(l):
		if val == prev_val:
			continue
		clusters.append([prev_val] * (i - cur_cluster_start))
		cur_cluster_start = i
		prev_val = val
	clusters.append([prev_val] * (len(l) - cur_cluster_start))
	return clusters[1:]
N = input().strip()
P = list(map(int, input().strip().split(' ')))
if all((P[i] <= P[i + 1] for i in range(len(P) - 1))):
	print('0.000000')
else:
	P.sort()
	subseqs = split_sorted_list_in_clusters(P)
	successful_permuts = 1
	for subseq in subseqs:
		successful_permuts *= math.factorial(len(subseq))
	total_permuts = math.factorial(len(P))
	E = total_permuts / successful_permuts
	print('{:6f}'.format(E))


from collections import Counter
N = int(input())
fact = [1, 1]
for i in range(2, 19):
	fact.append(fact[-1] * i)
xs = list(map(int, input().split()))
if xs == sorted(xs):
	print('0.000000')
else:
	c = Counter()
	for x in xs:
		c[x] += 1
	gs = 1
	for c in c.values():
		gs *= fact[c]
	res = fact[N] / gs
	print('%.6f' % res)


from collections import Counter
from functools import reduce
from operator import mul
from math import factorial
N = int(input())
P = list(map(int, input().split()))
P2 = P.copy()
P2.sort()
if all([P[i] == P2[i] for i in range(N)]):
	ncount = 0
else:
	C = Counter(P)
	ncount = factorial(N) / reduce(mul, map(factorial, C.values()))
print('{c:f}'.format(c=ncount))


import math
n = int(input())
prev = 0
sorted = True
arr = list(map(int, input().split()))
pres = [0] * 100
for i in range(n):
	if arr[i] < prev:
		sorted = False
	prev = arr[i]
	pres[arr[i] - 1] += 1
if sorted:
	print('0.000000')
else:
	f = math.factorial(n)
	k = 1.0
	for i in range(100):
		if pres[i] != 0:
			k *= math.factorial(pres[i])
	res = f / k
	print('%.6f' % res)


def fact(n):
	if n == 0:
		return 1
	else:
		return n * fact(n - 1)
n = int(input())
l = input()
a = [0] * 101
is_sorted = True
prev = -1
cur = 0
for i in l.split():
	cur = int(i)
	a[int(i)] += 1
	if prev > cur:
		is_sorted = False
	prev = cur
if is_sorted:
	print(0.0)
else:
	num = fact(n)
	den = 1
	for i in range(101):
		den *= fact(a[i])
	print('%.6f' % (num / den))


import math
import sys
n = int(sys.stdin.readline())
p = tuple((int(x) for x in sys.stdin.readline().split()))
sorted = True
for i in range(1, len(p)):
	if p[i - 1] > p[i]:
		sorted = False
		break
if sorted:
	print('%.6f' % 0)
else:
	total = math.factorial(len(p))
	count = {}
	for pi in p:
		if pi not in count:
			count[pi] = 0
		count[pi] += 1
	valid = 1
	for x in count.values():
		valid *= math.factorial(x)
	print('%.6f' % (total / valid))


from sys import stderr
from collections import Counter
from math import factorial

def read(f):
	return f(input())

def readlist(f):
	return [f(x) for x in input().split()]
N = read(int)
P = readlist(int)
Pc = Counter(P)
if all((P[i - 1] <= P[i] for i in range(1, N))):
	ans = 0
else:
	nP = factorial(N)
	nPsorted = 1
	for c in Pc.values():
		nPsorted *= factorial(c)
	ans = nP / nPsorted
print('%.6f' % ans)


import sys
import math

def fac(n, fac_dict=None):
	result = 1
	for i in range(2, n + 1):
		result *= i
	return result
f = sys.stdin
n = int(f.readline().rstrip())
l = [int(x) for x in f.readline().rstrip().split()]
is_sorted = True
for i in range(1, n):
	if l[i] < l[i - 1]:
		is_sorted = False
		break
if is_sorted:
	print('0.000000')
	sys.exit()
arrangement_count = fac(n)
sorted_number = 1
count_dict = dict()
for el in l:
	if el in count_dict.keys():
		count_dict[el] += 1
	else:
		count_dict[el] = 1
for c in count_dict.values():
	sorted_number *= fac(c)
sorted_proba = sorted_number / arrangement_count
test = arrangement_count / sorted_number
formatted = '{0:.6f}'.format(test)
print(formatted)
sys.exit()
sorted_proba_comp = 1 - sorted_proba
epsilon = 1e-07
last = 0
current = sorted_proba
power = sorted_proba * sorted_proba_comp
i = 2
while abs(last - current) >= epsilon:
	last = current
	current += i * power
	i += 1
	power *= sorted_proba_comp
rounded = round(current, 6)
formatted = '{0:.6f}'.format(current)
formatted = '{0:.6f}'.format(rounded)
print(formatted)


from itertools import groupby
import math
import functools
n = int(input())
unsortedList = list(map(int, input().split()))
sortedList = sorted(unsortedList)
if unsortedList == sortedList:
	print(0.0)
else:
	repetitions = [len(list(g)) for (k, g) in groupby(sortedList, lambda c: c)]
	p = math.factorial(n)
	p /= functools.reduce(lambda a, b: a * b, map(math.factorial, repetitions))
	print(p)


from math import factorial
from collections import Counter
n = int(input())
p = list(map(int, input().split()))
if all((p[i] <= p[i + 1] for i in range(len(p) - 1))):
	print('0.000000')
else:
	c = Counter(p)
	good_permutations = 1
	for v in c.values():
		good_permutations *= factorial(v)
	print('{:.6f}'.format(factorial(n) / good_permutations))


from math import factorial
from collections import Counter
N = int(input())
P = [int(x) for x in input().split()]
S = sorted(P)
if P == S:
	print('0.000000')
else:
	C = Counter(P)
	if len(C) == len(P):
		print('{:.6f}'.format(factorial(N)))
	else:
		d = 1
		for (k, v) in C.items():
			if v > 1:
				d *= factorial(v)
		print('{:.6f}'.format(factorial(N) // d))


import sys, math

def isSorted(inp):
	prev = inp[0]
	for i in inp[1:]:
		if i < prev:
			return False
		prev = i
	return True

def retDupProd(i):
	count = dict()
	for k in i:
		if k in count:
			count[k] += 1
		else:
			count[k] = 1
	retval = 1
	for key in count:
		retval *= math.factorial(count[key])
	return retval
n = int(input().strip())
i = list(map(int, input().strip().split(' ')))
if isSorted(i):
	print('0.000000')
else:
	dup_prod = retDupProd(i)
	permutations = math.factorial(n) / dup_prod
	print('{:.6f}'.format(round(permutations, 6)))


import math
N = int(input())
array = list(map(int, input().strip().split()))
d = {}
prev = 0
flag = True
for num in array:
	if num < prev:
		flag = False
	prev = num
	if num in d:
		d[num] += 1
	else:
		d[num] = 1
if flag:
	print('0.000000')
else:
	numOfPerm = math.factorial(N)
	for (key, value) in d.items():
		if value > 1:
			numOfPerm = numOfPerm / math.factorial(value)
	print('%.6f' % float(numOfPerm))


def solve():
	n = int(input())
	pool = [0] * 105
	a = []
	for i in input().strip().split():
		j = int(i)
		a.append(j)
		pool[j] = pool[j] + 1
	t = 1
	for i in range(2, n + 1):
		t = t * i
	for i in range(1, 101):
		if pool[i] > 1:
			k = 1
			for j in range(2, pool[i] + 1):
				k = k * j
			t = t / k
	prev = 0
	is_sorted = 1
	for i in a:
		if i >= prev:
			prev = i
		else:
			is_sorted = 0
			break
	if is_sorted == 0:
		print('%0.6f' % round(t, 6))
	else:
		print('%0.6f' % round(0, 6))
solve()


N = int(input())
import collections
import math
import sys
P = [int(n) for n in input().split()]
C = collections.Counter(P)
g = []
k = [r for r in P]
k.sort()
if len(P) == 1 or k == P:
	print('0.000000')
	sys.exit()
for i in C.values():
	if i != 1:
		g.append(i)
answer = math.factorial(N)
for i in g:
	answer /= float(math.factorial(i))
alltherestofthefutureprob = 1
print('%.6f' % round(answer, 6))
sys.exit()
p = 1 / answer
daysProb = p
q = 1 - p
EV = 0
oldEV = 0
q = 1
for t in range(1, 5000000):
	EV += t * p * q
	q *= 1 - p
print('%.6f' % round(EV, 6))
sys.exit()
day = 0
Expectation = 1
oldAnswer = 0
cattle = 23
while oldAnswer != cattle:
	oldAnswer = cattle
	day += 1
	q = 1 - daysProb
	daysProb = p * alltherestofthefutureprob
	Expectation += day * daysProb
	cattle = round(Expectation, 7)
print('%.6f' % round(Expectation, 6))


import math
from decimal import Decimal
n = int(input())
a = [int(num) for num in input().split(' ')]
b = list(a)
b.sort()
sorted = 1
for i in range(0, n):
	if a[i] != b[i]:
		sorted = 0
if sorted == 1:
	print('0.000000')
else:
	f = [0] * 200
	nom = Decimal(math.factorial(n))
	denom = Decimal(1.0)
	for i in range(0, n):
		f[a[i]] = f[a[i]] + 1
	for i in range(0, 101):
		denom = denom * math.factorial(f[i])
	ans = nom / denom
	print(round(ans, 6))


import sys
pp = [int(x) for x in input().strip().split(' ')]
N = pp[0]
arr = [int(x) for x in input().strip().split(' ')]

def factorial(x):
	mul = 1
	for i in range(1, x + 1):
		mul *= i
	return mul

def pruebaConvergencia(x):
	sum = 0
	proba = 0
	psum = 0
	for i in range(1, 10000000):
		proba = (1 - psum) * (1 / x)
		psum += proba
		sum += i * proba
	print(sum, x)

def calcularTiempo(N, arr):
	l = -1
	ordenada = True
	for i in arr:
		if i < l:
			ordenada = False
		l = i
	if ordenada:
		return 0
	for i in range(0, len(arr) - 1):
		for j in range(i + 1, len(arr)):
			if arr[i] > arr[j]:
				(arr[i], arr[j]) = (arr[j], arr[i])
	l = -1
	acc = 1
	div = 1
	for i in arr:
		if i == l:
			acc += 1
		else:
			div *= factorial(acc)
			acc = 1
		l = i
	div *= factorial(acc)
	combinaciones = factorial(N) / div
	return combinaciones
t = calcularTiempo(N, arr[:])
print('%.6f' % t)


import sys
from math import factorial
n = int(input())
s = input()
alist = [int(i) for i in s.split()]
l = len(alist)
sum = 1
i = 0
count = [0 for i in range(101)]
if sorted(alist) == alist:
	print('0')
	sys.exit(0)
for i in range(l):
	x = alist[i]
	count[x] = count[x] + 1
for i in range(101):
	sum = sum * factorial(count[i])
print('{:0.6f}'.format(factorial(l) / sum))


import math
n = int(input())
arr = input().strip().split()
arr = [int(x) for x in arr]
c = True
for i in range(1, len(arr)):
	if arr[i] < arr[i - 1]:
		c = False
if c:
	print(0.0)
else:
	temp = set(arr)
	temp = [arr.count(x) for x in temp]
	prob = math.factorial(len(arr))
	temp = [math.factorial(x) for x in temp]
	prod = 1
	for i in range(len(temp)):
		prod = prod * temp[i]
	p = prod * 1.0 / prob
	q = 1 - p
	ans = prob * 1.0 / prod
	print(ans)


import math
import decimal
N = int(input())
P = list(map(int, input().strip().split()))
c = dict()
for x in P:
	if x in c:
		c[x] += 1
	else:
		c[x] = 1
ans = decimal.Decimal(math.factorial(N))
for r in c.values():
	ans /= math.factorial(r)
if sorted(P) == P:
	print('0.000000')
else:
	print(round(ans, 6))


import math
n = int(input())
l = [int(i) for i in input().split()]
s = set(l)
div = 1
for i in s:
	div = div * math.factorial(l.count(i))
ans = float(math.factorial(n)) / float(div)
if sorted(l) == l:
	ans = 0.0
print('{0:.6f}'.format(round(ans, 6)))


from collections import Counter
import math

def prob(arr, n):
	c = Counter()
	p = 1.0
	if all((arr[i] <= arr[i + 1] for i in range(n - 1))):
		return 0.0
	for a in arr:
		c[a] += 1
	for k in c:
		p *= math.factorial(c[k])
	p = math.factorial(n) / p
	return p
n = int(input())
s = [int(x) for x in input().split(' ')]
print('%.6f' % prob(s, n))


from collections import defaultdict

def is_sorted(array):
	for i in range(1, len(array)):
		if array[i] < array[i - 1]:
			return False
	return True

def fact(n):
	f = 1
	for i in range(2, n + 1):
		f *= i
	return f
N = int(input())
P = tuple((int(x) for x in input().split()))
numbers = defaultdict(int)
for p in P:
	numbers[p] += 1
n_sorted = 1
for n in numbers.values():
	n_sorted *= fact(n)
n_total = fact(N)
res = n_total / n_sorted
if is_sorted(P):
	res = 0
print('{:0.6f}'.format(res))


import math
n = int(input())
tempArr = []
arr = []
divList = []
tempStr = input()
arr = list(map(int, tempStr.split()))
if arr != sorted(arr):
	for i in range(n):
		if arr[i] not in tempArr:
			x = arr.count(arr[i])
			if x > 1:
				divList.append(x)
				tempArr.append(arr[i])
	ans = math.factorial(n)
	if len(divList) != 0:
		for i in range(len(divList)):
			ans = ans / math.factorial(divList[i])
else:
	ans = 0
print('{0:.6f}'.format(ans))


from collections import Counter
from math import factorial
from functools import reduce
N = int(input())
nums = list(map(int, input().split()))
occ_per_num = list(Counter(nums).values())
if sorted(nums) == nums:
	print('0.000000')
else:
	expt_of_succ = factorial(N) / reduce(lambda x, y: x * y, map(factorial, occ_per_num), 1)
	print('{0:.6f}'.format(expt_of_succ))


import math
import sys
_ = int(input())
a = list(map(int, input().split()))
s = set(a)
b = [a.count(u) for u in sorted(s)]
print(sorted(s), file=sys.stderr)
print(b, file=sys.stderr)
v = math.factorial(len(a))
for u in b:
	v //= math.factorial(u)
print('v=%d' % v, file=sys.stderr)
e = 0
if v > 1:
	r = 1 / v
	e = 1 / (1 - r) + 1 / pow(1 - r, 2)
	e = v
if a == sorted(a):
	e = 0
print('%.6f' % e)


from collections import Counter
from functools import reduce
(n, ar) = (int(input()), list(map(int, input().split())))
factorial = lambda x: x * factorial(x - 1) if x else 1
print('{:.6f}'.format(0 if sorted(ar) == ar else factorial(n) / reduce(int.__mul__, map(factorial, Counter(ar).values()))))


def factorial(n):
	if n < 1:
		return 1
	return n * factorial(n - 1)
input()
numbers = [int(i) for i in input().strip().split(' ')]
if sorted(numbers) == numbers:
	print('{:f}'.format(0))
else:
	numbers.sort()
	order = [1]
	for i in range(1, len(numbers)):
		if numbers[i] == numbers[i - 1]:
			order[-1] += 1
		else:
			order.append(1)
	out = factorial(len(numbers))
	for i in order:
		out = out // factorial(i)
	print('{:f}'.format(out))


def isSorted(N, P):
	ans = True
	for i in range(N - 1):
		if P[i] > P[i + 1]:
			ans = False
			break
	return ans

def tally(P):
	ans = []
	for e in set(P):
		ans.append(P.count(e))
	return list(reversed(sorted(ans)))

def multichoose(N, P):
	T = tally(P)
	ans = 1
	n = N
	for t in T:
		for i in range(1, t + 1):
			ans *= n
			ans = ans // i
			n -= 1
	return ans

def Xsort(N, P):
	if isSorted(N, P):
		return '0.000000'
	return str(multichoose(N, P)) + '.000000'
N = int(input())
P = [int(x) for x in input().split()]
print(Xsort(N, P))


from math import factorial
from collections import Counter
(n, P) = (int(input()), [int(i) for i in input().split()])
if P == sorted(P):
	print(0)
else:
	repeats = 1
	for r in [factorial(v) for v in Counter(P).values()]:
		repeats *= r
	print(round(factorial(n) / repeats, 6))


from collections import defaultdict
from math import factorial
N = int(input().strip())
nums = [int(x) for x in input().strip().split(' ')]
freq = defaultdict(int)
sorted = True
freq[nums[0]] += 1
for i in range(1, N):
	freq[nums[i]] += 1
	if nums[i] < nums[i - 1]:
		sorted = False
if sorted:
	print('0.000000')
else:
	perms = 1
	for (_, v) in freq.items():
		perms *= factorial(v)
	print('{:0.6f}'.format(factorial(N) // perms))


import math
from collections import Counter
n = int(input())
numbers = list(map(int, input().split()))
if sorted(numbers) == numbers:
	print(0)
else:
	c = Counter(numbers)
	numerator = math.factorial(len(numbers))
	denominator = 1
	for x in c:
		denominator *= math.factorial(c[x])
	res = numerator / denominator
	print(res)
	_sum = 0


import math

def fac(num):
	fac = 1
	for i in range(1, num + 1):
		fac *= i
	return fac
N = int(input())
P = list(map(int, input().split(' ')))
pr = fac(N)
rep = [0] * 101
oldP = 0
sorted = True
for i in P:
	if i < oldP:
		sorted = False
	oldP = i
	rep[i] = rep[i] + 1
if sorted:
	print('0.000000')
	exit
else:
	for n in rep:
		if n > 0:
			pr /= fac(n)
	expectedPr = 1 / pr / math.pow(1 - 1 / pr, 2)
	print('%0.6f' % pr)


from sys import stdin
from math import factorial
from collections import defaultdict
from operator import mul
from functools import reduce
N = int(stdin.readline())
values = map(int, stdin.readline().split(' '))
nums = defaultdict(int)
sorted = True
prev_val = -1
for val in values:
	if val < prev_val:
		sorted = False
	nums[val] += 1
	prev_val = val
if not sorted:
	counts = list(nums.values())
	n_permutations = factorial(N)
	n_equivalent = reduce(mul, map(factorial, counts), 1)
	expected_wait = n_permutations / n_equivalent
	print('%.6f' % expected_wait)
else:
	print('0.000000')


import math
(N, P) = (int(input()), list(map(int, input().split())))
p = math.factorial(N)
for i in set(P):
	p //= math.factorial(P.count(i))
if all([P[i] >= P[i - 1] for i in range(1, N)]):
	p = 0
print('%.6f' % p)


def factorial(n):
	if n <= 1:
		return 1
	else:
		return n * factorial(n - 1)
n = int(input())
p = [int(s) for s in input().split()]
s = {}
for x in p:
	if x in s:
		s[x] += 1
	else:
		s[x] = 1
if all((p[i - 1] <= p[i] for i in range(1, n))):
	time = 0
else:
	time = factorial(n)
	for key in s:
		time /= factorial(s[key])
print('{0:.6f}'.format(time))


import math
from collections import Counter
from decimal import *
getcontext().prec = 6
N = input()
P = input()
arrayP = P.split()
fltArrayP = [float(i) for i in arrayP]
if sorted(fltArrayP) == fltArrayP:
	print(0)
else:
	dictP = dict()
	for i in fltArrayP:
		dictP[i] = dictP.get(i, 0) + 1
	dupDiv = 1
	for (k, v) in dictP.items():
		dupDiv *= math.factorial(int(v))
	print(math.factorial(int(N)) / dupDiv)


import itertools, math, collections
N = int(input())
perm = math.factorial(N)
seq = list(map(int, input().split()))
x = collections.Counter(seq)
if seq == sorted(seq):
	print('0.000000')
else:
	for v in x.values():
		perm /= math.factorial(v)
	print('%.6f' % perm)


n = int(input())
a = [int(item) for item in input().split()]
flag = 1
fact = [1] * 20
for i in range(2, 19):
	fact[i] = i * fact[i - 1]
p = [0] * 101
p[a[0]] += 1
for i in range(1, n):
	if a[i] < a[i - 1]:
		flag = 0
	p[a[i]] += 1
prod = 1
for i in range(1, 101):
	prod = prod * fact[p[i]]
if flag == 1:
	print(0)
else:
	print(fact[n] / prod)


import math

def is_sorted(a):
	return all((x <= y for (x, y) in zip(a, a[1:])))

def unique_permutations(a):
	repititions = {}
	for i in a:
		repititions[i] = repititions.get(i, 0) + 1
	premutations = math.factorial(len(a))
	for r in repititions.values():
		premutations /= math.factorial(r)
	return premutations

def solve(a):
	if is_sorted(a):
		return 0
	else:
		return unique_permutations(a)

def main():
	N = int(input())
	a = list(map(int, input().split()))
	print(solve(a))
main()


import copy

def factorial(k):
	return k * factorial(k - 1) if k >= 2 else 1
n = int(input())
a = [int(x) for x in input().strip().split(' ')]
c = copy.copy(a)
c.sort()
sorteda = True
for x in range(n):
	if a[x] != c[x]:
		sorteda = False
		break
if sorteda:
	print('0.000000')
else:
	b = [0 for x in range(101)]
	for x in a:
		b[x] += 1
	ret = factorial(n)
	for y in range(101):
		ret /= factorial(b[y])
	print('%.6f' % ret)


import math, collections
n = int(input())
a = list(map(int, input().split()))
done = all([a[i] <= a[i + 1] for i in range(n - 1)])
good = 1
for v in collections.Counter(a).values():
	good *= math.factorial(v)
good /= math.factorial(n)
ans = 1 / good
if done:
	ans = 0
print('{0:.6f}'.format(ans))


N = int(input())
L = [int(l) for l in input().split(' ')]
from collections import Counter
C = Counter(L)
if sorted(L) == L:
	print('{:.6f}'.format(0))
else:
	p = 1
	j = 0
	for k in C.values():
		for i in range(1, k + 1):
			j += 1
			p *= j / i
	print('{:.6f}'.format(p))


def fact(n):
	k = 1
	for i in range(1, n + 1):
		k = k * i
	return k
n = int(input())
arr = [int(x) for x in input().split()]
ctr = []
bubbly = []
for i in arr:
	if i in ctr:
		x = ctr.index(i)
		bubbly[x] += 1
	else:
		ctr.append(i)
		bubbly.append(1)
uniques = len(ctr)
ans = fact(n)
for i in bubbly:
	ans = ans / fact(i)
ans = float(ans)
if sorted(arr) == arr:
	ans = 0.0
ans = round(ans, 6)
print(ans)


from math import factorial

def issorted(l):
	return all((l[i] <= l[i + 1] for i in range(len(l) - 1)))
N = int(input())
arr = [int(tmp) for tmp in input().split()]
arr_dict = {}
for item in arr:
	if item not in arr_dict:
		arr_dict[item] = 0
	arr_dict[item] += 1
if issorted(arr):
	print(0)
else:
	den = factorial(N)
	for key in arr_dict:
		den /= factorial(arr_dict[key])
	print(den)


from collections import Counter
import math
n = int(input())
a = [int(x) for x in input().split()]
if sorted(a) == a:
	print('0')
else:
	count_a = Counter(a)
	rep_a = list(count_a.values())
	s = 1
	for x in rep_a:
		s *= math.factorial(x)
	p = s / math.factorial(n)
	if p < 1:
		print('%.6f' % (1 / p))
	else:
		print(0)


from collections import defaultdict
from math import factorial as fac
n = int(input())
d = defaultdict(lambda : 0)
sorted = True
prev = -1
for x in map(int, input().split()):
	if x < prev:
		sorted = False
	prev = x
	d[x] += 1
if sorted:
	print('0.000000')
else:
	res = 1
	for x in d.keys():
		res *= fac(d[x])
	print('%.6f' % (fac(n) / res))


from collections import Counter
from operator import mul
from functools import reduce
from math import factorial
N = int(input())
P = [int(x) for x in input().split()]
if sorted(P) == P:
	print(0)
else:
	counter = Counter(P)
	perms = factorial(N)
	good_perms = reduce(mul, [factorial(x) for x in counter.values()])
	prob = good_perms / perms
	print(1 / prob)


import math

def fac(n):
	return math.factorial(n)

def uniquify(P):
	unique_P = sorted(list(set(P)))
	occurr_P = [sum([i == n for i in P]) for n in unique_P]
	return (unique_P, occurr_P)

def prod(a):
	out = 1
	for i in a:
		out *= i
	return out

def probability_to_sort(P):
	N = len(P)
	(unique_P, occurr_P) = uniquify(P)
	return prod([fac(n) for n in occurr_P]) / fac(N)

def expected_time_to_sort(P):
	if sum([i == j for (i, j) in zip(P, sorted(P))]) == len(P):
		return 0
	return 1 / probability_to_sort(P)
N = int(input())
P = [int(i) for i in input().split(' ')]
print('{:.6f}'.format(expected_time_to_sort(P)))


from collections import Counter

def fact(n):
	f = 1
	for i in range(1, n + 1):
		f *= i
	return f
n = int(input())
f = fact(n)
kist = []
kist[0:n] = input().split()
kist = list(map(int, kist))
if sorted(kist) != kist:
	ans = f
	for (k, v) in Counter(kist).items():
		ans /= fact(v)
	format(ans, '.6f')
	print(ans)
else:
	print(0)


import math
from collections import Counter
N = int(input())
L = [int(x) for x in input().split(' ')]
if sorted(L) == L:
	res = 0.0
else:
	occurrences = Counter(L).values()
	nsorted = 1.0
	for x in occurrences:
		nsorted *= math.factorial(x)
	p = nsorted / math.factorial(N)
	res = 1 / p
print('%0.6f' % res)


from math import factorial
from fractions import Fraction

def isSorted(a):
	for i in range(1, len(a)):
		if a[i] < a[i - 1]:
			return False
	return True
_ = int(input())
a = list(map(int, input().split()))
if isSorted(a):
	print(0)
else:
	a.sort()
	(req, cnt) = (1, 1)
	for i in range(len(a)):
		if i and a[i - 1] == a[i]:
			cnt += 1
		else:
			cnt = 1
		req *= cnt
	f = Fraction(factorial(_), req)
	print('%.6f' % f)


from math import factorial
from fractions import Fraction

def isSorted(a):
	for i in range(1, len(a)):
		if a[i] < a[i - 1]:
			return False
	return True
_ = int(input())
a = list(map(int, input().split()))
if isSorted(a):
	print(0)
else:
	a.sort()
	(req, cnt) = (1, 1)
	for i in range(len(a)):
		if i and a[i - 1] == a[i]:
			cnt += 1
		else:
			cnt = 1
		req *= cnt
	f = Fraction(factorial(_), req)
	print('%.6f' % f)


import math, functools
input()
xs = [int(x) for x in input().split()]
if xs == sorted(xs):
	print('0.000000')
	exit()
counts = {}
for x in xs:
	if x in counts:
		counts[x] += 1
	else:
		counts[x] = 1
mul = lambda a, b: a * b
facts = [math.factorial(counts[count]) for count in counts]
ans = math.factorial(len(xs)) / functools.reduce(mul, facts)
print('%.6f' % ans)


n = input()
n = int(n)
listofnos = input().split(' ')
listofnos = [int(n) for n in listofnos]
if listofnos == sorted(listofnos):
	answer = 0
else:
	from collections import Counter
	counted = Counter(listofnos)
	from math import factorial
	denom = 1
	for repeats in counted.values():
		denom *= factorial(repeats)
	answer = factorial(n) / denom
answer = round(answer, 6)
print('%.6f' % answer)


from functools import reduce
from collections import Counter
fact = lambda x: reduce(lambda y, z: y * z, range(1, x + 1), 1)
a = int(input())
nums = list(map(int, input().strip().split()))
if nums != sorted(nums):
	p = fact(a) / reduce(lambda x, y: x * y, map(fact, Counter(nums).values()))
	print(p)
else:
	print(0)


from math import factorial
from collections import Counter

def binom(n, k):
	return factorial(n) // factorial(k) // factorial(n - k)

def compute(P):
	if sorted(P) == P:
		return 0
	n = len(P)
	ans = factorial(n)
	for k in Counter(P).values():
		ans /= factorial(k)
	return ans
N = int(input())
P = list(map(int, input().split()))
print('%.6f' % compute(P))


N = int(input())
A = [int(a) for a in input().split()]
B = [A.count(b) for b in set(A)]

def frac(n):
	k = 1
	for i in range(2, n + 1):
		k *= i
	return k
if A == sorted(A):
	print('%.6f' % 0)
else:
	P = 1 / frac(N)
	for b in B:
		P *= frac(b)
	s = P * (1 - P) / P ** 2 + 1
	print('%.6f' % s)


from collections import Counter
from math import factorial
n = int(input())
ps = [int(x) for x in input().split()]

def issorted(seq):
	return sorted(seq) == seq
c = Counter(ps)
res = factorial(n)
for (k, v) in c.items():
	res //= factorial(v)
if issorted(ps):
	print(0)
else:
	print(res)


n = int(input())
a = list(map(int, input().split()))
m = {}
for i in a:
	if i in m:
		m[i] += 1
	else:
		m[i] = 1
from math import factorial as f
ch = f(n)
zn = 1
for i in m:
	zn *= f(m[i])
if a == sorted(a):
	print('0.000000')
else:
	print(format(ch / zn, '.6f'))


from collections import Counter
from math import factorial
n = int(input())
a = list(map(int, input().split()))
srtd = True
for i in range(n - 1):
	if a[i] > a[i + 1]:
		srtd = False
		break
if srtd:
	print('0.000000')
else:
	dups = 1
	for i in Counter(a).values():
		dups *= factorial(i)
	ev = factorial(n) / dups
	print('{:8.6f}'.format(ev))


N = int(input())
v = list(map(int, input().split()))
from math import factorial
r = [0] * 101
f = factorial(N)
for e in v:
	r[e] += 1
for e in r:
	f //= factorial(e)
if sorted(v) == v:
	print(0)
else:
	print(f)


import math
n = int(input())
p = list(map(int, input().split()))
if sorted(p) == p:
	print(0)
else:
	ans = math.factorial(n)
	for e in set(p):
		ans //= math.factorial(p.count(e))
	print(ans)


def fact(n):
	if n == 0 or n == 1:
		return 1
	return n * fact(n - 1)
n = int(input())
l = list(map(int, input().split()))
l2 = sorted(l)
issorted = True
for i in range(n):
	if not l[i] == l2[i]:
		issorted = False
p = [0 for i in range(101)]
for i in range(n):
	p[l[i]] += 1
if issorted:
	print('0.000000')
else:
	ans = fact(n)
	for i in p:
		ans /= fact(i)
	print('%.6f' % ans)


from math import factorial
N = int(input())
P = input().split()
P0 = [int(x) for x in P]
P = [int(x) for x in P]
P.sort()
if P0 == P:
	print(0)
else:
	s = factorial(N)
	c = 1
	for i in range(1, N):
		if P[i] != P[i - 1]:
			s /= factorial(c)
			c = 1
		else:
			c += 1
	s /= factorial(c)
print('%.6f' % s)


import math

def is_sorted(l):
	return all((l[i] <= l[i + 1] for i in range(len(l) - 1)))
N = int(input())
P = input()
P = [int(p) for p in P.split(' ')]
D = {}
for i in range(N):
	if P[i] in D:
		D[P[i]] += 1
	else:
		D[P[i]] = 1
PI = 1
for key in D.keys():
	PI *= math.factorial(D[key])
answer = math.factorial(len(P)) / PI
if is_sorted(P):
	print('%.6f' % 0)
else:
	print('%.6f' % answer)


from collections import Counter

def fact(n):
	f = 1
	while n > 0:
		f *= n
		n -= 1
	return f

def solve(P):
	if P == sorted(P):
		return 0
	count = Counter(P)
	p = fact(sum(count.values()))
	for v in count.values():
		p //= fact(v)
	return p
N = int(input())
P = list(map(int, input().split()))
print('%.6f' % solve(P))


import sys
factorialCache = [1.0, 2.0, 6.0, 24.0, 120.0, 720.0, 5040.0, 40320.0, 362880.0, 3628800.0, 39916800.0, 479001600.0, 6227020800.0, 87178291200.0, 1307674368000.0, 20922789888000.0, 355687428096000.0, 6402373705728000.0]
inputs = []
lineNumber = 0
N = None
arr = []
for line in sys.stdin:
	if lineNumber == 0:
		N = float(line)
	else:
		arr = list(map(float, line.strip().split(' ')))
	lineNumber = 1
repeats = {}
for elem in arr:
	if elem in repeats:
		repeats[elem] += 1
	else:
		repeats[elem] = 1
currentElem = arr[0]
alreadySorted = True
for elem in arr:
	if elem >= currentElem:
		currentElem = elem
	else:
		alreadySorted = False
		break
if alreadySorted:
	print('0.000000')
else:
	P = 1
	for (key, value) in repeats.items():
		if value > 1:
			P *= factorialCache[int(value - 1)]
	answer = factorialCache[int(N - 1)] / P
	print(format(answer, '.6f'))


n = int(input())
p = [int(x) for x in input().split()]
is_sorted = True
for i in range(n - 1):
	if p[i] > p[i + 1]:
		is_sorted = False
p = sorted(p)
num = 1
for i in range(1, n + 1):
	num *= i
den = 1
v = 1
for i in range(1, n):
	if p[i] == p[i - 1]:
		v += 1
		den *= v
	else:
		v = 1
if is_sorted:
	print('%.6f' % 0.0)
else:
	print('%.6f' % (num / den))


import math
from collections import Counter

def isSorted(arr):
	for i in range(len(arr) - 1):
		if arr[i] > arr[i + 1]:
			return False
	return True
n = int(input())
numbers = list(map(int, input().split()))
if isSorted(numbers):
	print(str.format('{0:.6f}', 0.0))
else:
	expectedTime = math.factorial(n)
	for i in Counter(numbers).values():
		expectedTime /= math.factorial(i)
	print(str.format('{0:.6f}', expectedTime))


fact = [1] * 19
for i in range(1, 19):
	fact[i] = fact[i - 1] * i
N = int(input())
P = [int(x) for x in input().split()]
ord = 1
for i in range(1, N):
	if P[i - 1] > P[i]:
		ord = 0
		break
if ord:
	print(0)
else:
	C = {}
	for x in P:
		C[x] = C.get(x, 0) + 1
	y = fact[N]
	for x in C.values():
		y //= fact[x]
	print(y)