#P8991. [北大集训 2021] 出题高手

[北大集训 2021] 出题高手

题目背景

CTT2021 D3T2

题目描述

Alice 是一个出题高手。

Alice 每天都会出一道题,这样 nn 天过去,她就出了 nn 道题了。

n+1n+1 天,Alice 没有出题,她打算从之前的 nn 道题中选择若干道组成一个比赛。方便起见,她决定这些选择的题目得是连续的一个时间段出的,也就是这些题目必须形如:第 ll 天到第 rr 天出的所有题目(1lrn1\le l \le r \le n)。

Alice 还给每个题目一个评分,第 ii 个题目的评分为 ai(1000ai1001)a_i(-1000 \le a_i \le 1001) ,评分越高代表这道题越偏智商,评分越低说明这道题越偏码力。

Alice 希望组成的比赛具备特色,也即整体偏向代码或者整体偏向智商。一场以 Alice 第 ll 天到第 rr 天出的题目组成的比赛的特色程度定义为 (lrai)2rl+1\Large \frac{(\sum_l^r a_i)^2}{r-l+1} ,Alice 想要最大化这个特色程度。

现在,对于 mm 个形如 qli,qriql_i,qr_i 的询问,你需要回答如果将 Alice 能选择的题目限定在第 qliql_iqriqr_i 天出的题,Alice 能组成的特色程度最大的比赛的特色程度是多少,你需要以分数的形式输出这个特色程度。

由于 Alice 出题的水平过于高超,你可以认为每道题的评分是随机生成的。

输入格式

输入的第一行包含一个正整数 nn

输入的第二行包含 nn 个整数 a1ana_1 \dots a_n,代表 Alice 对第 ii 天所出的题的评分。

输入的第三行包含一个正整数 mm

接下来 mm 行,每行输入两个正整数 qli,qriql_i,qr_i,表示询问。

输出格式

mm 行,每行两个整数 pi,qip_i,q_i,满足 gcd(pi,qi)=1\gcd(p_i,q_i)=1,表示答案为 piqi\frac{p_i}{q_i},若答案为 00,则 pi=0p_i=0qi=1q_i=1

5
-962 -445 -613 -9 920
3
1 5
3 5
1 3

4080400 3
846400 1
4080400 3

提示

子任务 n=n= m=m= 分值
11 20002000 100000100000 55
22 100000100000 11 1515
33 500000500000 3030
44 100000100000 50005000 1515
55 300000300000 3535

对于 第 22 个和第 33 个子任务,保证所有询问满足 qli=1ql_i = 1qri=nqr_i = n

所有的 aia_i 保证满足 1000ai1001-1000 \le a_i \le 1001。且对于 aia_i ,数据生成方式为每次独立地从 [1000,1001][-1000,1001] 中等概率随机选取一个整数。