Average Maximization

We are given an array A of N positive integers. A subsequence X = [x₀, x₁, …, xₘ₋₁] (with m ≥ 2) is called a closed sequence if its two endpoints are preserved and every interior element is strictly greater than both endpoints. In other words, if m ≥ 3 then for every k with 1 ≤ k ≤ m−2, we require

[ x[k] > x[0] \quad \text{and} \quad x[k] > x[m-1]. ]

Note that any sequence of length 2 is closed, and sequences of length 0 or 1 are not defined as closed.

We are allowed to perform the following elimination operation on any sequence X of length K (K ≥ 2):

Select a contiguous closed subsequence X[i], X[i+1], …, X[j] (with 0 ≤ i < j ≤ K−1) and remove all the interior elements X[i+1], …, X[j−1]. That is, the sequence becomes

[ X[0], \cdots, X[i], X[j], \cdots, X[K-1]. ]

Define f(X) to be the maximum possible average (i.e. the ratio of the sum to the count) obtainable from the final sequence after performing any number (zero or more) of elimination operations. It turns out that, no matter how the operations are done, the first and last elements of the original sequence remain—so the final sequence is always a subsequence of X with the first and last elements preserved.

A necessary and sufficient condition for a subsequence B (with B[0] = X[0] and B[last] = X[m-1]) to be obtainable is that for every pair of consecutive indices p and q in B (if q > p+1) the segment

[ X[p], X[p+1], \dots, X[q] ]

must be closed; that is,

[ \min_{p < k < q} X[k] > \max(X[p], X[q]). ]

The task is: Given an array A[0..N−1], process several queries. Each query gives indices i and j (with 0 ≤ i < j ≤ N−1) such that the subarray A[i..j] is closed. For each such query, compute f(A[i..j]) and output it as a fraction s/t where s and t are positive integers (between 1 and 10^18) and f(A[i..j]) = s/t exactly.

You need to implement the following two functions:

void initialize(vector A);

This function is called only once before any other call and provides you with the entire array A.

array maximum_average(int i, int j);

For a query (i, j), the function should return the fraction representing f(A[i], A[i+1], …, A[j]).

Note: The test data guarantee that the answer for every query can be written in the form s/t with 1 ≤ s, t ≤ 10^18.

Example: For instance, if A = [1, 3, 2, 100, 97, 98, 2, 3, 4, 1] then one may achieve f(A) = 43 by performing the following operations:

1. Choose i = 0 and j = 2 on the segment [1, 3, 2] (which is closed because 3 > 1 and 3 > 2) and remove the interior element to obtain [1, 2, 100, 97, 98, 2, 3, 4, 1].
2. Next, choose i = 5 and j = 8 on [2, 3, 4, 1] (closed since 3 > 2 and 4 > 1) and remove the interior elements, resulting in [1, 2, 100, 97, 98, 2, 1].

The final sequence has sum 301 and 7 elements, so its average is 301/7 = 43.

Your solution must compute the maximum achievable average exactly.

inputFormat

The input is given from standard input. It consists of multiple lines. The first line contains an integer N (the size of the array). The second line contains N positive integers representing array A. The third line contains an integer Q representing the number of queries. Then Q lines follow, each containing two integers i and j (0-indexed) such that A[i..j] is a closed sequence.

outputFormat

For each query, output on a separate line two space‐separated positive integers s and t such that f(A[i..j]) = s/t.

sample

10
1 3 2 100 97 98 2 3 4 1
1
0 9

301 7