P12743 [POI 2016 R3] 勤奋的约翰尼 Diligent Johny

翻译来自于 [LibreOJ](https://loj.ac/p/5039)。

**题目译自 [XXIII Olimpiada Informatyczna — III etap](https://sio2.mimuw.edu.pl/c/oi23-3/dashboard/) [Pracowity Jaś](https://szkopul.edu.pl/problemset/problem/_cVmDXXn2TjF0dF1rW6eazA0/statement/)** 今天是小 Johny 的生日……但这是一道严肃的算法题，可怜的 Johny 没有收到玩具、游戏或电脑作为礼物。相反，他得到了一堆充满数字的长数组、树形结构、遍布隧道和立交桥的奇异地图，以及长达 1048576 个符号的 Fibonacci 和 Thue-Morse 序列前缀等教育礼物。在这些礼物中，他最喜欢的是一个包含 $1$ 到 $n$ 的正整数排列的数组。很快，Johny 开始思考这个排列的字典序前驱排列†是什么。聪明如他，很快解决了这个问题，并立即想到如何通过数组支持的唯一操作——交换任意两个单元的内容——将当前排列转换为其前驱。Johny 发现这个任务如此引人入胜，以至于他不断将每个排列转换为其字典序前驱。 沉迷于排列变换的 Johny 完全忽略了生日派对的宾客。宾客们觉得这既有趣又有些失礼。很快，有人意识到 Johny 会在达到字典序最小的单位排列 $1,2,\ldots,n$ 时停下来。问题在于，这需要多长时间？请帮助宾客们解答这个问题，假设每次交换耗时一秒。由于 Johny 极其勤奋，这个过程可能很长，宾客们只关心交换次数对 $10^9+7$ 取模的结果。他们可以每隔 $10^9+7$ 秒检查一次，看 Johny 是否终于完成了。 $^\dagger$对于排列 $P = (p_1, \ldots, p_n)$ 和 $Q = (q_1, \ldots, q_n)$，若在最小的满足 $p_j \neq q_j$ 的索引 $j$ 处有 $p_j < q_j$，则称 $P$ 在字典序上小于 $Q$（记为 $P < Q$）。若 $P < Q$ 且不存在排列 $R$ 满足 $P < R < Q$，则称 $P$ 是 $Q$ 的字典序前驱。

第一行包含一个正整数 $n$，表示 Johny 收到的排列长度。 第二行包含 $n$ 个互不相同的整数 $p_1, p_2, \ldots, p_n$ $(1 \leq p_i \leq n)$，表示排列的元素。

输出一行，包含一个整数，表示 Johny 停止前进行的交换次数对 $10^9+7$ 取模的结果。

**样例 1 解释** Johny 经历的字典序递减排列序列为 $(3,1,2), (2,3,1), (2,1,3), (1,3,2), (1,2,3)$。为此，他总共进行了 $2+1+2+1=6$ 次交换。 **附加样例** 1. $n=10$，排列为 $1,2,3,\ldots,10$。 2. $n=5$，一个随机 $5$ 元素的排列。 3. $n=100$，排列为 $100,99,98,\ldots,1$。 详细子任务附加限制及分值如下表所示。 | 子任务 | 附加限制 | 分值 | | :---: | :--: | :---: | | $1$ | $n \leq 10$ | $15$ | | $2$ | $n \leq 5000$ | $37$ | | $3$ | $n \leq 1000000$，排列为 $n, n-1, \ldots, 1$ | $15$ | | $4$ | $n \leq 1000000$ | $33$ |