A sequence $x[0], \dots, x[m-1]$ of length $m$ ($m \ge 2$) consisting of positive integers is called a blocked sequence if it satisfies the following condition: * For every integer $k$ such that $1 \le k \le m-2$, $x[k] > x[0]$ and $x[k] > x[m-1]$.

In other words, $x$ is a blocked sequence if both its endpoints are smaller than all elements located between them.

For example, $[3, 7, 8, 4, 2]$ and $[7, 7]$ are blocked sequences, while $[5, 8, 4, 6, 7]$ and $[3, 3, 4]$ are not. Note that by definition, all sequences of length 2 are blocked sequences, and sequences of length 1 or less cannot be blocked sequences.

Given a sequence $X[0], \dots, X[K-1]$ of length $K$, a removal operation is an operation that chooses a pair $(i, j)$ such that $X[i], \dots, X[j]$ is a blocked sequence, and removes $X[i+1], \dots, X[j-1]$ from the sequence (i.e., changes the sequence to $X[0], \dots, X[i], X[j], \dots, X[K-1]$).

Let $f(X)$ be the maximum possible average of the final sequence that can be obtained by using these removal operations as desired (you may use them zero or more times).

For example, $f([1, 3, 2, 100, 97, 98, 2, 3, 4, 1]) = 43$. This can be achieved by applying the removal operations as follows: Choose $i = 0, j = 2$ to change the sequence to $[1, 2, 100, 97, 98, 2, 3, 4, 1]$. Choose $i = 5, j = 8$ to change the sequence to $[1, 2, 100, 97, 98, 2, 1]$. * The final sequence is $[1, 2, 100, 97, 98, 2, 1]$, and its average is $(1 + 2 + 100 + 97 + 98 + 2 + 1)/7 = 43$.

You are given a sequence $A[0], \dots, A[N-1]$ of length $N$ consisting of positive integers. You must write a program that calculates the value of $f(A[i], \dots, A[j])$ whenever a pair $(i, j)$ is given such that $A[i], \dots, A[j]$ is a blocked sequence.

Note

The average of a sequence $x[0], \dots, x[m-1]$ of length $m$ is defined as the sum of the elements of the sequence divided by the length $m$, i.e., $\frac{x[0]+x[1]+\dots+x[m-1]}{m}$.

For a sequence $x$, $x[i], \dots, x[j]$ is a sequence of length $j-i+1$ consisting of the elements from the $i$-th element to the $j$-th element of $x$. For example, if $x = [3, 5, 7, 2, 9]$, then $x[1], \dots, x[3]$ is $[5, 7, 2]$, and $x[4], \dots, x[4]$ is $[9]$.

Implementation Details

You must implement the following functions:

void initialize(std::vector<int> A)

• This function is called exactly once, before any other functions are called.
• $A$: An integer array of size $N$.
• You can implement any necessary preprocessing or global variable settings for subsequent function calls in this function.

std::array<long long, 2> maximum_average(int i, int j)

• It is given that $0 \le i < j \le N-1$ and $A[i], \dots, A[j]$ is a blocked sequence.
• This function must return $[s, t]$ when $f(A[i], \dots, A[j]) = s/t$.
  • $s$ and $t$ must be integers between $1$ and $10^{18}$. It can be proven that for all inputs satisfying the constraints, the answer can always be expressed as a fraction of this form.
  • $s/t$ does not have to be an irreducible fraction.
• This function is called $Q$ times.

You must not execute any input/output functions in any part of your submitted source code.

Constraints

• $2 \le N \le 300\,000$
• $1 \le Q \le 600\,000$
• $1 \le A[i] \le 10\,000\,000$ for all $i$ ($0 \le i \le N-1$)
• For all calls to maximum_average, $0 \le i < j \le N-1$ and $A[i], \dots, A[j]$ is a blocked sequence.

Subtasks

1. (5 points) $N \le 15$
2. (6 points) $N \le 50$
3. (13 points) $N \le 250$
4. (7 points) $A[i] \le 4$ for all $i$ ($0 \le i \le N-1$)
5. (12 points) $N \le 5\,000$
6. (17 points) $A$ is a blocked sequence. $Q = 1$, and maximum_average(0, N-1) is called. That is, it is sufficient to find the answer for the entire sequence $A$.
7. (8 points) $A[i] \le 20$ for all $i$ ($0 \le i \le N-1$)
8. (32 points) No additional constraints.

Examples

Example 1

Consider the case where $N = 10, A = [2, 4, 3, 9, 9, 9, 9, 9, 9, 1]$. The grader calls the following functions in order:

initialize([2, 4, 3, 9, 9, 9, 9, 9, 9, 1])
maximum_average(0, 2)
maximum_average(0, 9)

$A[0], \dots, A[2] = [2, 4, 3]$ cannot have its average increased from the initial state through removal operations, so the maximum average is $(2 + 4 + 3)/3 = 9/3$. Therefore, maximum_average(0, 2) can return $[3, 1]$ or $[9, 3]$, etc.

On the other hand, in $A[0], \dots, A[9] = [2, 4, 3, 9, 9, 9, 9, 9, 9, 1]$, choosing $i = 0, j = 2$ and removing $4$ increases the average from $64/10$ to $60/9$, which is the maximum possible average. Therefore, maximum_average(0, 9) can return $[60, 9]$ or $[20, 3]$, etc.

Note

The sample grader receives input in the following format: Line 1: $N$ Line 2: $A[0] \ A[1] \ \dots \ A[N-1]$ Line 3: $Q$ Line $3 + k$ ($1 \le k \le Q$): $i[k] \ j[k]$ (arguments for the $k$-th call to maximum_average)

The sample grader outputs the following: * Line $k$: The two integers of the array returned by the $k$-th call to maximum_average.

Note that the sample grader may differ from the grader used in actual grading.