若一个由正整数组成的长度为 $m$ ($m \ge 2$) 的序列 $x[0], \dots, x[m-1]$ 满足以下条件，则称其为“封闭序列”：

• 对于所有 $1$ 到 $m-2$ 之间的整数 $k$，都有 $x[k] > x[0]$ 且 $x[k] > x[m-1]$。

也就是说，如果序列 $x$ 的首尾元素都小于中间的所有元素，则 $x$ 是一个封闭序列。

例如，$[3, 7, 8, 4, 2]$ 和 $[7, 7]$ 是封闭序列，而 $[5, 8, 4, 6, 7]$ 和 $[3, 3, 4]$ 不是。请注意，根据定义，所有长度为 $2$ 的序列都是封闭序列，而长度小于等于 $1$ 的序列不可能是封闭序列。

对于一个长度为 $K$ 的序列 $X[0], \dots, X[K-1]$，“提取操作”是指选择一对 $(i, j)$ 使得 $X[i], \dots, X[j]$ 是一个封闭序列，并从序列中移除 $X[i+1], \dots, X[j-1]$（即将序列变为 $X[0], \dots, X[i], X[j], \dots, X[K-1]$）。

定义 $f(X)$ 为通过任意次数（包括零次）的提取操作后，所能得到的最终序列的平均值的最大值。

例如，$f([1, 3, 2, 100, 97, 98, 2, 3, 4, 1]) = 43$，可以通过以下操作实现：

• 选择 $i = 0, j = 2$，将序列变为 $[1, 2, 100, 97, 98, 2, 3, 4, 1]$。
• 选择 $i = 5, j = 8$，将序列变为 $[1, 2, 100, 97, 98, 2, 1]$。
• 最终序列为 $[1, 2, 100, 97, 98, 2, 1]$，其平均值为 $(1 + 2 + 100 + 97 + 98 + 2 + 1)/7 = 43$。

给定一个由正整数组成的长度为 $N$ 的序列 $A[0], \dots, A[N-1]$。你需要编写一个程序，在每次给定一对 $(i, j)$ 使得 $A[i], \dots, A[j]$ 为封闭序列时，计算 $f(A[i], \dots, A[j])$ 的值。

参考

长度为 $m$ 的序列 $x[0], \dots, x[m-1]$ 的平均值定义为序列元素之和除以序列长度 $m$，即 $\frac{x[0]+x[1]+\dots+x[m-1]}{m}$。

对于序列 $x$，$x[i], \dots, x[j]$ 表示由序列 $x$ 中第 $i$ 个元素到第 $j$ 个元素组成的长度为 $j-i+1$ 的序列。例如，当 $x = [3, 5, 7, 2, 9]$ 时，$x[1], \dots, x[3]$ 为 $[5, 7, 2]$，$x[4], \dots, x[4]$ 为 $[9]$。

实现细节

你需要实现以下函数：

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

• 该函数仅被调用一次，且在所有其他函数调用之前执行。
• $A$：长度为 $N$ 的整数数组。
• 如果后续函数调用需要预处理或设置全局变量，可以在此函数中实现。

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

• 保证 $0 \le i < j \le N-1$ 且 $A[i], \dots, A[j]$ 是一个封闭序列。
• 当 $f(A[i], \dots, A[j]) = s/t$ 时，该函数应返回 $[s, t]$。
  • $s$ 和 $t$ 必须是 $1$ 到 $10^{18}$ 之间的整数。可以证明，对于所有满足约束条件的输入，答案总能表示为该形式的分数。
  • $s/t$ 不需要是最简分数。
• 该函数会被调用 $Q$ 次。

提交的源代码中不得执行任何输入输出函数。

数据范围

• $2 \le N \le 300\,000$
• $1 \le Q \le 600\,000$
• 对于所有 $i$，$1 \le A[i] \le 10\,000\,000$ ($0 \le i \le N-1$)
• 对于所有 maximum_average 调用，$0 \le i < j \le N-1$ 且 $A[i], \dots, A[j]$ 是封闭序列。

子任务

1. (5分) $N \le 15$
2. (6分) $N \le 50$
3. (13分) $N \le 250$
4. (7分) 对于所有 $i$，$A[i] \le 4$ ($0 \le i \le N-1$)
5. (12分) $N \le 5\,000$
6. (17分) $A$ 是一个封闭序列。$Q = 1$，且调用 maximum_average(0, N-1)。即只需计算整个序列 $A$ 的答案。
7. (8分) 对于所有 $i$，$A[i] \le 20$ ($0 \le i \le N-1$)
8. (32分) 无额外约束。

样例

样例 1

考虑 $N = 10, A = [2, 4, 3, 9, 9, 9, 9, 9, 9, 1]$ 的情况。

评测系统按顺序调用以下函数：

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]$ 无法通过提取操作使平均值大于初始状态，因此最大平均值为 $(2 + 4 + 3)/3 = 9/3$。因此，maximum_average(0, 2) 可以返回 $[3, 1]$ 或 $[9, 3]$ 等。

另一方面，在 $A[0], \dots, A[9] = [2, 4, 3, 9, 9, 9, 9, 9, 9, 1]$ 中，选择 $i = 0, j = 2$ 并移除 $4$，平均值从 $64/10$ 增加到 $60/9$，这是可能达到的最大平均值。因此，maximum_average(0, 9) 可以返回 $[60, 9]$ 或 $[20, 3]$ 等。

样例评测程序

样例评测程序按以下格式接收输入：

• 第 1 行：$N$
• 第 2 行：$A[0] \ A[1] \ \dots \ A[N-1]$
• 第 3 行：$Q$
• 第 $3 + k$ 行 ($1 \le k \le Q$)：$i[k] \ j[k]$（第 $k$ 次调用 maximum_average 函数的参数）

样例评测程序输出：

• 第 $k$ 行：第 $k$ 次调用的 maximum_average 返回的数组中的两个整数

请注意，样例评测程序可能与实际评测中使用的评测程序不同。