题目背景

请勿用 C++14 (GCC 9) 提交本题

你需要在程序开头加入如下代码：

#include<vector>
#include<array>
void initialize(std::vector<int> A);
std::array<long long, 2> maximum_average(int i, int j);

题目描述

题目译自 2024년도 국제정보올림피아드 대표학생 선발고사 - 1차 선발고사 T1 「평균 최대화」

给定一个由正整数组成的长度为 $m$ $(m \geq 2)$ 的序列 $x[0], \cdots, x[m-1]$，如果该序列满足以下条件，则称其为封闭序列：

• 对于所有 $k$ $(1 \leq k \leq m-2)$，$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], \cdots, X[K-1]$，定义剔除操作为选择一个封闭序列 $X[i], \cdots, X[j]$，并从序列中移除 $X[i+1], \cdots, X[j-1]$（即将序列变为 $X[0], \cdots, X[i], X[j], \cdots, 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], \cdots, A[N-1]$。对于每个给定的封闭序列 $(i, j)$，你需要计算 $f(A[i], \cdots, A[j])$ 的值。

你需要实现以下函数：

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

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

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

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

输入格式

示例评测程序按以下格式读取输入：

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

输出格式

示例评测程序输出：

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

10
2 4 3 9 9 9 9 9 9 1
2
0 2
0 9

3 1
20 3

提示

对于所有输入数据，满足：

• $2 \leq N \leq 3\cdot 10^5$
• $1 \leq Q \leq 6\cdot 10^5$
• 对于所有 $i$ $(0 \leq i \leq N-1)$，$1 \leq A[i] \leq 10^7$
• 对于所有 maximum_average 调用，$0 \leq i < j \leq N-1$，且 $A[i], \cdots, A[j]$ 是一个封闭序列。

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
$1$	$5$	$N \leq 15$
$2$	$6$	$N \leq 50$
$3$	$13$	$N \leq 250$
$4$	$7$	对于所有 $i$ $(0 \leq i \leq N-1)$，$A[i] \leq 4$
$5$	$12$	$N \leq 5000$
$6$	$17$	$A$ 是一个封闭序列；$Q=1$，且调用 maximum_average(0, N-1)，即只需计算整个序列 $A$ 的答案
$7$	$8$	对于所有 $i$ $(0 \leq i \leq N-1)$，$A[i] \leq 20$
$8$	$32$	无附加限制