#2059. 出题高手

出题高手

出题高手

题目描述

标题: 出题高手 - Problem - QOJ.ac

#3276. 出题高手

Statistics

The problem was used in the following contests:

Alice 是一个出题高手。

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

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

Alice 还给每个题目一个评分,第 i 个题目的评分为 ai(−1000≤ai≤1001) ,评分越高代表这道题越偏智商,评分越低说明这道题越偏码力。

Alice 希望组成的比赛具备特色,也即整体偏向代码或者整体偏向智商。一场以 Alice 第 l 天到第 r 天出的题目组成的比赛的特色程度定义为 (∑lrai)2r−l+1 ,Alice 想要最大化这个特色程度。

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

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

输入格式

从标准输入读入数据。

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

输入的第二行包含 n 个整数 a1…an , 代表 Alice 对第 i 天所出的题的评分。

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

接下来 m 行,每行输入两个正整数 qli,qri ,表示询问。

输出格式

输出到标准输出。

共 m 行,每行两个整数 pi,qi , 满足 gcd(pi,qi)=1,表示答案为 piqi ,若答案为 0 ,则 pi=0,qi=1。

样例数据

样例输入

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

样例输出

4080400 3
846400 1
4080400 3

数据范围与提示

子任务 n= m= 分值 1 2000 100000 5 2 100000 1 15 3 500000 30 4 100000 5000 15 5 300000 35

对于 第 2 个和第 3 个子任务,保证所有询问满足 qli=1,qri=n。

所有的 ai 保证满足 −1000≤ai≤1001 。

且对于 ai ,数据生成方式为每次独立地从 [−1000,1001] 中等概率随机选取一个整数。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

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