Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1920. Номер перестановки
Дерево отрезков, декартово дерево, √-декомпозицияОлимпиадные задачи на русском языке
| 16/07/2013 | Лето 2013-11 (C) |
| 14/07/2016 | Лето 2016 - 9 (B) |
Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Перестановкой из `N` элементов называется упорядоченный набор
из `N` различных чисел от 1 до `N`. Количество всех перестановок из `N` элементов равно `N!\ =\ 1\ *\ 2\ *\ 3\ *\ …\ *\ N`. Требуется найти номер заданной перестановки в лексикографическом порядке. Например, для `N=3` лексикографический порядок перестановок выглядит следующим образом:
(1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1).
Таким образом, перестановка (3,1,2) имеет номер 5 в этой последовательности.
В первой строке входного файла записано число `N` (`1\ ≤\ N\ ≤\ 100000`) — количество элементов в перестановке. Во второй строке даны `N` целых чисел — элементы данной перестановки.
В выходной файл выведите единственное целое число — номер данной перестановки в лексикографическом порядке. Так как это число может быть очень большим выведите остаток от его деления на 1000000007 (`10^9+7`).
Пример ввода 1
3 3 1 2
Пример вывода 1
5
Пример ввода 2
4 2 3 1 4
Пример вывода 2
9
