题目描述

给定一个长度为 $n$ 的整数序列

$$a=(a_1,a_2,\ldots,a_n).$$

对于每个 $k\in\{1,2,\ldots,n\}$，定义

$$min_k=\min\{a_1,a_2,\ldots,a_k\},\qquad max_k=\max\{a_1,a_2,\ldots,a_k\}.$$

于是可以给序列 $a$ 关联一个闭区间序列

$$minmax=([min_1,max_1],[min_2,max_2],\ldots,[min_n,max_n]).$$

如果序列 $minmax$ 中的所有区间两两不同，也就是说不存在两个完全相同的区间，则称序列 $a$ 是一个彩色序列。

例如，若 $a=(7,4,9)$，则

$$minmax=([7,7],[4,7],[4,9]).$$

其中没有两个相同的区间，所以 $a$ 是彩色序列。

相反，若 $a=(4,9,7)$，则

$$minmax=([4,4],[4,9],[4,9]).$$

区间 $[4,9]$ 出现了两次，所以 $a$ 不是彩色序列。

现在考虑所有可以由序列 $a$ 的元素重新排列得到的、互不相同的彩色序列，并按字典序从小到大排序。记这样的序列个数为 $NSC$。

例如，对于 $a=(7,4,9)$，它的 $6$ 个排列中只有 $NSC=4$ 个是彩色序列，按字典序为：

1. $(4,7,9)$；
2. $(7,4,9)$；
3. $(7,9,4)$；
4. $(9,7,4)$。

任务

给定一个序列 $a$，它不一定是彩色序列。你需要根据输入中的任务编号 $c$ 完成以下三类任务之一：

1. 求可以由 $a$ 重排得到的彩色序列个数 $NSC$。由于答案可能很大，只需要输出 $NSC\bmod 1\,000\,000\,007$。
2. 已知输入序列 $a$ 是彩色序列，求它在所有由 $a$ 重排得到的彩色序列按字典序排序后的列表中的位置 $p$。
3. 给定 $q\in\{1,2,\ldots,NSC\}$，求由 $a$ 重排得到的按字典序排序后的第 $q$ 个彩色序列。

输入格式

第一行包含一个整数 $c\in\{1,2,3\}$，表示需要解决的任务编号。

• 如果 $c=1$：

  • 第二行包含一个整数 $n$；
  • 第三行包含 $n$ 个整数，表示一个不一定是彩色序列的序列 $a$。

• 如果 $c=2$：

  • 第二行包含一个整数 $n$；
  • 第三行包含 $n$ 个整数，表示一个已知为彩色序列的序列 $a$。

• 如果 $c=3$：

  • 第二行包含两个整数 $n,q$；
  • 第三行包含 $n$ 个两两不同的整数，表示一个不一定是彩色序列的序列 $a$。

输出格式

包含一行。

• 如果 $c=1$，输出 $NSC\bmod 1\,000\,000\,007$。
• 如果 $c=2$，输出一个整数 $p$，表示输入序列 $a$ 在所有彩色重排序列的字典序列表中的位置。
• 如果 $c=3$，输出 $n$ 个整数，表示由 $a$ 重排得到的、字典序第 $q$ 小的彩色序列。

数据范围与限制

• $2\le n\le 300\,000$；
• $-1\,000\,000\,000\le a_i\le 1\,000\,000\,000$；
• $1\le p,q\le 1\,000\,000\,000$；
• $p,q\in\{1,2,\ldots,NSC\}$。

子任务

子任务	分值	限制
1	9	$c=1,\ n\le 20$
2	7	$c=1,\ 21\le n\le 300\,000$
3	10	$c=2,\ 1\le p\le n$
4		$c=2,\ NSC-p\le n$
5		$c=2,\ n\le 20$
6	12	$c=2,\ 21\le n\le 300\,000$
7	10	$c=3,\ 1\le q\le n$
8		$c=3,\ NSC-q\le n$
9		$c=3,\ n\le 20$
10	12	$c=3,\ 21\le n\le 300\,000$

样例

样例 1

输入

1
4
1 5 3 8

输出

8

解释

共有 $8$ 个不同的彩色序列：

1: 1 3 5 8
2: 3 1 5 8
3: 3 5 1 8
4: 3 5 8 1
5: 5 3 1 8
6: 5 3 8 1
7: 5 8 3 1
8: 8 5 3 1

样例 2

输入

2
4
5 3 1 8

输出

5

解释

在所有彩色重排序列按字典序排序后的列表中，输入序列位于第 $5$ 位。

样例 3

输入

3
4 7
5 3 1 8

输出

5 8 3 1

解释

第 $7$ 个彩色序列为 5 8 3 1。