C-置换_牛客挑战赛35

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

我们定义一个长度为 ${n}$ 的置换为 $\lbrace 1,2, \dots ,n \rbrace$ 到其本身的一个双射（即一种对应关系 ${f}$ ，把 ${1}$ 到 ${n}$ 的每个数和另一个 ${1}$ 到 ${n}$ 的数（可以为其本身）一一对应起来）。
例如 ${[3,1,2,5,4]}$ 为长度为 ${5}$ 的一个置换，意义为 ${f(1)=3 , f(2) = 1 , f(3) = 2 , f(4) = 5 , f(5) = 4}$ 。其循环节为 ${(3,1,2)(5,4)}$ 。循环节 $(a_{1},a_{2}, \dots a_{m})$ 的含义为在置换中 $f(a_{1}) = a_{2} , f(a_{2}) = a_{3} , \dots f(a_{m}) = a_{1}$ 。可以发现一个置换可以唯一地拆分成各个循环节。
另一方面，每一个置换 ${F}$ 都可以唯一地对应一个排列 ${P}$ ，使得 $P_{i} = f(i)$ 。在这种条件下，可以比较两个置换的字典序——只要比较其对应排列的字典序即可。我们称置换 $f_{1}$ 比 $f_{2}$ 字典序大当且仅当 $f_{1}$ 对应的排列 $p_{1}$ 字典序比 $f_{2}$ 对应的排列 $p_{2}$ 字典序大。
现在给出长度为 ${n}$ 的置换 ${F}$ ，求所有长度为 ${n}$ 且字典序严格大于 ${F}$ 的置换 ${F'}$ 的循环节个数之和。

输入描述:

第一行数字
接下来一行个互不相同的数字表示该置换

输出描述:

一行一个数表示答案模的结果

示例1

输入

复制

3
2 3 1

输出

复制

说明

大于该置换的置换有两个
可拆分为
可拆分为
总计三个循环节

示例2

输入

复制

6
2 1 6 5 3 4

输出

复制

题目描述

输入描述:

输出描述:

输入

输出

说明

输入

输出

备注: