{"raw_statement":[{"iden":"background","content":"CTT2021 D3T2"},{"iden":"statement","content":"Alice 是一个出题高手。\n\nAlice 每天都会出一道题，这样 $n$ 天过去，她就出了 $n$ 道题了。\n\n第 $n+1$ 天，Alice 没有出题，她打算从之前的 $n$ 道题中选择若干道组成一个比赛。方便起见，她决定这些选择的题目得是**连续**的一个时间段出的，也就是这些题目必须形如：第 $l$ 天到第 $r$ 天出的所有题目（$1\\le l \\le r \\le n$）。\n\nAlice 还给每个题目一个评分，第 $i$ 个题目的评分为 $a_i(-1000 \\le a_i \\le 1001)$ ，评分越高代表这道题越偏智商，评分越低说明这道题越偏码力。\n\nAlice 希望组成的比赛具备特色，也即整体偏向代码或者整体偏向智商。一场以 Alice 第 $l$ 天到第 $r$ 天出的题目组成的比赛的特色程度定义为 $\\Large \\frac{(\\sum_l^r a_i)^2}{r-l+1}$ ，Alice 想要**最大化**这个特色程度。\n\n现在，对于 $m$ 个形如 $ql_i,qr_i$ 的询问，你需要回答如果将 Alice  能选择的题目限定在第 $ql_i$ 到 $qr_i$ 天出的题，Alice 能组成的特色程度最大的比赛的特色程度是多少，你需要以分数的形式输出这个特色程度。\n\n由于 Alice 出题的水平过于高超，你可以认为每道题的评分是**随机生成**的。\n"},{"iden":"input","content":"\n输入的第一行包含一个正整数 $n$。\n\n输入的第二行包含 $n$ 个整数 $a_1 \\dots a_n$，代表 Alice 对第 $i$ 天所出的题的评分。\n\n输入的第三行包含一个正整数 $m$。\n\n接下来 $m$ 行，每行输入两个正整数 $ql_i,qr_i$，表示询问。\n"},{"iden":"output","content":"共 $m$ 行，每行两个整数 $p_i,q_i$，满足 $\\gcd(p_i,q_i)=1$，表示答案为 $\\frac{p_i}{q_i}$，若答案为 $0$，则 $p_i=0$，$q_i=1$。"},{"iden":"note","content":"| 子任务 |   $n=$   |   $m=$   | 分值 |\n| :----: | :------: | :------: | :--: |\n|  $1$   |  $2000$  | $100000$ | $5$  |\n|  $2$   | $100000$ |   $1$    | $15$ |\n|  $3$   | $500000$ |   $1$    | $30$ |\n|  $4$   | $100000$ |  $5000$  | $15$ |\n|  $5$   | $100000$ | $300000$ | $35$ |\n\n\n\n对于 第 $2$ 个和第 $3$ 个子任务，保证所有询问满足 $ql_i = 1$，$qr_i = n$。\n\n所有的 $a_i$ 保证满足 $-1000 \\le a_i \\le 1001$。且对于 $a_i$ ，数据生成方式为每次独立地从 $[-1000,1001]$ 中等概率随机选取一个整数。\n"}],"translated_statement":null,"sample_group":[["5\n-962 -445 -613 -9 920\n3\n1 5\n3 5\n1 3\n","4080400 3\n846400 1\n4080400 3\n"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}