Цілком невідсортовані послідовності#9882

Цілком невідсортовані послідовності

1 секунда

256 мегабайтів

Складна

Нещодавно вас призначили провідним науковим співробітником NASA — Національної асоціації алгоритмів сортування (National Association for Sorting Algorithms). Вітаємо! Ваш головний обов'язок — тестувати алгоритми сортування, які розробляє ваша команда. На щастя, цього року у NASA великий бюджет, і вам вдалося закупити найновіші цілі числа для тестування алгоритмів сортування.

Як провідний науковий співробітник, ви чудово знаєте, що алгоритми оцінюють за їхньою поведінкою на найгірших вхідних даних. Тому для тестування алгоритмів сортування вам потрібні послідовності, які неврівноважено впорядковані настільки, наскільки це можливо.

Нехай дано послідовність чисел $(a_{1}, \dots, a_{n})$ (a_1, \ldots, a_n). Будемо говорити, що елемент $a_{k}$ a_k стоїть на своєму місці, якщо $a_{j} \geq a_{k}$ a_j \ge a_k для всіх індексів $j > k$ j > k і $a_{j} \leq a_{k}$ a_j \le a_k для всіх індексів $j < k$ j < k. Наприклад, у послідовності

(1, 3, 2, 3, 4, 6, 5, 5)

(1, 3, 2, 3, 4, 6, 5, 5)

на своїх місцях стоять елементи $1$ , друге входження $3$ та $4$ . Зауважимо, що послідовність відсортована тоді і тільки тоді, коли всі її елементи стоять на своїх місцях. Послідовність називається цілком невідсортованою, якщо жоден її елемент не стоїть на своєму місці.

Скільки цілком невідсортованих послідовностей можна отримати, переставляючи елементи заданої послідовності цілих чисел? Дві послідовності $(b_{1}, \dots, b_{n})$ (b_1, \ldots, b_n) та $(c_{1}, \dots, c_{n})$ (c_1, \ldots, c_n) вважаються різними, якщо $b_{i} \neq = c_{i}$ b_i \ne c_i для деякого індексу $i \in {1, \dots, n}$ i \in \{1, \ldots, n\}. Оскільки це число може бути дуже великим, виведіть його за модулем $1 0^{9} + 9$ 10^9 + 9.

Вхідні дані

У першому рядку задано ціле число $n (1 \leq n \leq 5000)$ n~(1 \le n \le 5000).

У другому рядку задано $n$ цілих чисел $a_{1}, \dots, a_{n} (0 \leq a_{i} \leq 1 0^{9})$ a_1, \ldots, a_n~(0 \le a_i \le 10^9).

Вихідні дані

Виведіть одне ціле число — кількість цілком невідсортованих послідовностей, які можна отримати перестановкою елементів $a_{1}, \dots, a_{n}$ a_1, \ldots, a_n, за модулем $1 0^{9} + 9$ 10^9 + 9.

Приклади

Приклад 1

Приклад 2

Приклад 3