$1s1024MB(water.in/out)$
题目描述
对于长为 $m$ 的序列 $x$，认为它是好的当且仅当 $m\ge 2$，且 $\max(x_1,x_m)<\min(x_2,x_3,\cdots,x_{m-1})$。
考虑序列长为 $n$ 的 $a$，你可以进行任意次操作，每次可以选择一个区间 $[l,r]$ 满足 $a_l,a_{l+1},\cdots,a_r$ 这个序列是好的，然后删除 $a_{l+1}\cdots a_{r-1}$，接下来序列会变成 $a_1,a_2,\cdots,a_{l-1},a_l,a_r,a_{r+1},\cdots,a_n$。你希望最大化最终序列的所有元素的平均值。设 $f(a)$ 为上述问题的答案。
给定长为 $N$ 的序列 $A$，有 $Q$ 次询问，每次给出 $l,r$，你需要输出 $f(A[l\cdots r])$ 的值。具体来说，设答案化为最简分数后为 $\frac{x}{y}$，你需要输出一行两个正整数 $x,y$ 表示答案。
保证每次询问给出的 $l,r$ 满足：$A[l\cdots r]$ 是一个好的序列。
输入格式
第 $1$ 行一个整数 $N$ 。
第 $2$ 行 $n$ 个数表示序列 $A$ 。
第 $3$ 行一个整数 $Q$ 。
接下来 $Q$ 行，每行两个整数 $l_i,r_i$。
输出格式
输出共 $Q$ 行表示答案。
样例
样例 1 输入
10
2 4 3 9 9 9 9 9 9 1 2
1 3
1 10样例 1 输出
3 1
20 3样例 2
见选手目录下 $\rm water/ex\_water2.in$ 和 $\rm water/ex\_water2.out$ 。
该样例满足子任务 $3$ 的限制。
样例 3
见选手目录下 $\rm water/ex\_water3.in$ 和 $\rm water/ex\_water3.out$ 。
该样例满足子任务 $5$ 的限制。
样例 4
见选手目录下 $\rm water/ex\_water4.in$ 和 $\rm water/ex\_water4.out$ 。
该样例满足子任务 $6$ 的限制。
数据范围
$2\le N\le 3\times 10^5,1\le Q\le 6\times 10^5,1\le A_i\le 10^9,1\le l < r\le N$。
$\rm Subtask\ 1(5pts)$：$n\leq 15$。
$\rm Subtask\ 2(5pts)$：$n\leq 50$。
$\rm Subtask\ 3(10pts)$：$n\leq 250$ 。
$\rm Subtask\ 4(10pts)$：$A_i\leq 4$ 。
$\rm Subtask\ 5(15pts)$：$n\leq 5000$。
$\rm Subtask\ 6(20pts)$：保证 $A$ 序列是好的且 $Q=1$ ，$l_1=1,r_1=n$。
$\rm Subtask\ 7(10pts)$：$A_i\leq 20$。
$\rm Subtask\ 8(30pts)$：无特殊限制。