https://www.acmicpc.net/problem/31283

# KOITST 24 Maximising The Average

An array consisting of positive integers with a length of $m$ ($m ≥ 2$) $x[0], \cdots, x[m - 1]$ is defined as a blocked array if it satisfies the following condition:

- For all integers $k$ from $1$ to $m - 2$, $x[k] > x[0]$ and $x[k] > x[m - 1]$.

In other words, if the two end elements of $x$ are smaller than all the elements located between them, then $x$ is a blocked array.

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

Given a array $X[0], \cdots, X[K - 1]$ of length $K$, the **extraction operation** selects $(i, j)$ where $X[i], \cdots, X[j]$ form a blocked array and removes $X[i + 1], \cdots, X[j - 1]$ from the array (i.e., replaces the array with $X[0], \cdots, X[i], X[j], \cdots, X[K - 1]$).

You are given an array $A$ of length $N$. Then, you have to answer $Q$ queries of the following form:

Given $i$ and $j$, where $A[i], \cdots, A[j]$ forms a blocked array, determine the **maximum average** of the the subarray $A[i], \cdots, A[j]$ , after applying the **extraction operation** any number of times.

For example, Consider the subarray $[1, 3, 2, 100, 97, 98, 2, 3, 4, 1]$. The **extraction operations** can be applied as follows:

1. Choose $i = 0$, $j = 2$ to change the sequence to $[1, 2, 100, 97, 98, 2, 3, 4, 1]$.
2. Choose $i = 5$, $j = 8$ to change the sequence to $[1, 2, 100, 97, 98, 2, 1]$.

The final array is $[1, 2, 100, 97, 98, 2, 1]$, and its average is $(1 + 2 + 100 + 97 + 98 + 2 + 1)/7 = 43$.

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

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

# Implementation

Function List and Definitions

You need to implement the following functions:

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

This function is called only once and is called before any other function calls.

$A$: an integer array of size $N$.

If there is any preprocessing or global variable setup required for subsequent function calls, it should be implemented in this function.

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

You are given $0 ≤ i < j ≤ N - 1$, such that $A[i], \cdots, A[j]$ forms a blocked array.

This function should return $[s, t]$ where $f(A[i], \cdots , A[j]) = s/t$.

$s$ and $t$ should be integers ranging from $1$ to $10^{18}$. It can be proven that for all inputs satisfying the constraints, the answer can always be expressed as a fraction in this form.

$s/t$ does not necessarily need to be in its reduced form.

This function is called $Q$ times.

No input/output function should be executed in any part of the submitted source code.

# Constraints

* $2 ≤ N ≤ 300, 000$ 
* $1 ≤ Q ≤ 600, 000$ 
* For all $i$, $1 ≤ A[i] ≤ 10, 000, 000$ ($0 ≤ i ≤ N - 1$)
* For all maximum_average calls, $0 ≤ i < j ≤ N - 1$, and $A[i], \cdots, A[j]$ forms a blocked array.

# Subtask

Subtask 6:

$A$ is a blocked array.

$Q = 1$ and `maximum_average(0, N - 1)` is called. In other words, it is sufficient to find the answer for the entire array $A$.

# Examples

## Example 1

Consider the case where $N = 10$ and $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], \cdots , A[2] = [2, 4, 3]$ cannot increase the average from the initial state through extraction 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, selecting $i = 0$ and $j = 2$ from $A[0], \cdots , A[9] = [2, 4, 3, 9, 9, 9, 9, 9, 9, 1]$ to remove $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.