레이팅 미적용-3mm
-10mm
You have recently been promoted to lead scientist at NASA, the National Association for Sorting Algorithms. Congratulations! Your primary responsibility is testing the sorting algorithms that your team produces. Fortunately, NASA has a large budget this year, and you were able to buy some state of the art integers you can use to test the sorting algorithms.
As the lead scientist, you are well aware that algorithms are tested by their behaviour on worst case inputs. So, to test sorting algorithms, you need sequences that are as unsorted as possible.
Given a sequence of numbers \((a_1,\ldots,a_n)\) we say that an element \(a_k\) is sorted if for all indices \(j\) such that $j >
k\(, \)a_j \geq a_k\( and\ for\ all\ indices \)j\( such\ that \)j < k\(, \)a_j \leq a_k$. For example, in $$
(1, 3, 2, 3, 4, 6, 5, 5)
$$ the sorted elements are the 1, the second occurrence of 3, and the 4. Note that a sequence is sorted if and only if all its elements are sorted. A sequence is called entirely unsorted if none of its elements are sorted.
Given a sequence of integers, what is the number of entirely unsorted sequences you can make by permuting its elements? Two sequences \((b_1, \dots, b_n)\) and \((c_1, \dots, c_n)\) are considered to be different if there is some index \(i \in \left\{1, \dots, n \right\}\) for which \(b_i \neq c_i\). Because the number of permutations may be very large, please give it modulo \(10^9 + 9\).
The input starts with an integer \(1 \leq n \leq 5000\). Then follows a single line with \(n\) integers \(a_1, \ldots, a_n\), with \(0 \leq a_i \leq 10^9\) for all \(i\).
Print a single integer: the number of entirely unsorted sequences you can make by permuting the \(a_i\), modulo \(10^9 + 9\).
4
0 1 2 3
14
5
1 1 2 1 1
1
13
1 2 3 4 5 6 7 8 9 10 11 12 13
298600727