Background

CTT2021 D3T2

Problem Description

Alice is an expert at setting problems.

Alice sets one problem every day. After $n$ days, she has set $n$ problems.

On day $n+1$, Alice does not set a new problem. She plans to choose some problems from the previous $n$ problems to form a contest. For convenience, she decides that the chosen problems must come from a continuous time interval, meaning they must be exactly all problems from day $l$ to day $r$ ($1 \le l \le r \le n$).

Alice also gives each problem a rating. The rating of the $i$-th problem is $a_i(-1000 \le a_i \le 1001)$. A higher rating means the problem is more about IQ, while a lower rating means it is more about coding.

Alice wants the contest to have a distinctive style, i.e., overall leaning toward coding or overall leaning toward IQ. For a contest formed by all problems from day $l$ to day $r$, its distinctiveness is defined as $\Large \frac{(\sum_l^r a_i)^2}{r-l+1}$. Alice wants to maximize this distinctiveness.

Now, for $m$ queries of the form $ql_i, qr_i$, you need to answer: if Alice is only allowed to choose problems from day $ql_i$ to day $qr_i$, what is the maximum possible distinctiveness of the contest she can form? You need to output this value as a fraction.

Since Alice is far too good at setting problems, you may assume that the rating of each problem is randomly generated.

Input Format

The first line contains a positive integer $n$.

The second line contains $n$ integers $a_1 \dots a_n$, representing Alice's rating for the problem set on day $i$.

The third line contains a positive integer $m$.

The next $m$ lines each contain two positive integers $ql_i, qr_i$, representing a query.

Output Format

Output $m$ lines. Each line contains two integers $p_i, q_i$ with $\gcd(p_i, q_i) = 1$, indicating the answer is $\frac{p_i}{q_i}$. If the answer is $0$, then $p_i = 0$ and $q_i = 1$.

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

4080400 3
846400 1
4080400 3

Hint

For Subtasks $2$ and $3$, all queries satisfy $ql_i = 1$ and $qr_i = n$.

All $a_i$ satisfy $-1000 \le a_i \le 1001$. Also, for each $a_i$, the testdata is generated by independently choosing an integer uniformly at random from $[-1000, 1001]$ each time.

Translated by ChatGPT 5