1439. RMQ 板子拼接

对于一个数组 a[]a[],定义 RMQ(L,R)RMQ(L,R) 是数组下标区间 [L,R][L,R] 的最大值,也就是 maxi=LRai\max_{i=L}^{R}a_i

现在给定长度为 nn 的全排列数组 a[]a[ ],接下来有 mm 次询问。

每次询问中,给定 kk 个不同的数 p[]p[ ],你可以从中有放回地随机抽取两个数 px,pyp_x, p_y,不妨设 pxpyp_x \leq p_y

现在问你对于 a[]a[]RMQ(px,py)RMQ(p_x,p_y) 有哪几种情况,这些情况出现的概率各是多大。

输入

第一行输入一个正整数 n (1n105)n \ (1 \leq n \leq 10^5)

接下来输入一行 nn 个正整数 a1,a2,...,an (1ain)a_1,a_2,...,a_n \ (1 \leq a_i \leq n)

接下来一行输入一个正整数 m (1m2×105)m \ (1\leq m \leq 2 \times 10^5)

接下来 mm 行,每行首先输入一个正整数 k (1k105)k \ (1 \leq k \leq 10^5),然后紧跟着 kk 个正整数 p1,p2,...,pk (1pin)p_1,p_2,...,p_k \ (1 \leq p_i \leq n)

数据保证 k2×105\sum k \leq 2 \times 10^5

输出

对于每个查询,首先按照可能出现的得分升序输出得分情况,然后输出该得分情况的概率。

概率用一个既约分数 P/QP/Q 表述。

样例

标准输入 复制文本
5
1 3 5 2 4
3
1 1
2 1 5
5 5 4 3 2 1
标准输出 复制文本
1 1/1
1 1/4
4 1/4
5 1/2
1 1/25
2 1/25
3 3/25
4 3/25
5 17/25
登录以提交代码。
单点时限 2 秒
内存限制 1024 MB
提交 8
通过 5