有两行森林。第一行森林有 $N$ 棵树，从左到右依次编号为 $0$ 到 $N-1$。第二行森林有 $M$ 棵树，同样从左到右编号为 $0$ 到 $M-1$。第一行森林中第 $i$ $(0 \leq i \leq N-1)$ 棵树的高度是 $A[i]$，第二行森林中第 $j$ $(0 \leq j \leq M-1)$ 棵树的高度是 $B[j]$。
你想要制作一个木筏，材料将从这两片森林中砍伐而来。假设木筏由左至右的树高依次为 $H[0], H[1], \ldots, H[L-1]$，其稳定性定义为：
$$ \max_{0 \leq s \leq l \leq L-1} (\min(H[s], \ldots, H[l]) \times (l - s + 1)) $$
木筏的树木必须遵循以下规则：
- 砍伐的所有树都要用于木筏。
- 从第一行森林砍来的树必须保持原有顺序，即如果树 $X$ 在森林中位于树 $Y$ 左侧，那么在木筏上 $X$ 也必须在 $Y$ 左侧。
- 从第二行森林砍来的树同样需保持原有顺序。
你决定砍伐第一行森林中从 $0$ 到 $N-1$ 的全部 $N$ 棵树，但第二行森林中具体砍哪些树尚未确定。你需要回答 $Q$ 个编号从 $0$ 到 $Q-1$ 的问题，这些问题由长度为 $Q$ 的数组 $L$ 和 $R$ 表示。第 $k$ $(0 \leq k \leq Q-1)$ 个问题是：若从第二行森林砍伐编号在 $L[k]$ 到 $R[k]$ 之间的树，木筏的最大稳定性是多少？
实现细节
你需要实现以下函数：
std::vector<long long> max_stability(std::vector<int> A, std::vector<int> B,
std::vector<int> L, std::vector<int> R)A：长度为 $N$ 的整数数组，表示 KOI 森林树高。B：长度为 $M$ 的整数数组，表示 IOI 森林树高。L, R：长度为 $Q$ 的整数数组，表示每次询问的范围。- 函数需返回一个长度为 $Q$ 的整数数组 $C$，其中对于 $0 \leq k \leq Q-1$，$C[k]$ 表示用 KOI 森林所有树及 IOI 森林编号从 $L[k]$ 到 $R[k]$ 的树制作木筏时，可能的最大稳定性。
- 每个测试用例中，该函数只被调用一次。
你提交的代码不得包含任何输入输出函数。
样例一
假设 $N=5$，$M=4$，$Q=2$，$A=[3,3,1,6,1]$，$B=[3,5,7,6]$，$L=[0,0]$，$R=[1,3]$。
评测程序调用：
max_stability([3, 3, 1, 6, 1], [3, 5, 7, 6], [0, 0], [1, 3])当 $L[0]=0, R[0]=1$ 时，最大稳定性为 $12$。例如：
- 木筏从左到右依次为 KOI 的 $0$、$1$ 号树，IOI 的 $0$、$1$ 号树，KOI 的 $2$、$3$、$4$ 号树，高度为 $H=[3,3,3,5,1,6,1]$。
- 取 $[0, 3]$，最小高度 $\min(H[0], H[1], H[2], H[3]) = 3$，宽度 $4$，稳定性 $3 \times 4 = 12$。
当 $L[1]=0, R[1]=3$ 时，最大稳定性为 $20$。例如：
- 木筏从左到右依次为 KOI 的 $0$、$1$、$2$ 号树，IOI 的 $0$、$1$、$2$、$3$ 号树，KOI 的 $3$、$4$ 号树，高度为 $H=[3,3,1,3,5,7,6,6,1]$。
- 取 $[4, 7]$，最小高度 $\min(H[4], H[5], H[6], H[7]) = 5$，宽度 $4$，稳定性 $5 \times 4 = 20$。
函数应返回 $[12, 20]$。
样例二
评测程序调用：
max_stability([9, 9, 9, 9, 9], [1, 2, 3, 4, 5, 6, 7, 8], [0, 0, 0, 0, 0, 0, 0, 0], [0, 1, 2, 3, 4, 5, 6, 7])函数应返回 $[45, 45, 45, 45, 45, 45, 45, 49]$。
样例三
评测程序调用：
max_stability([1000000000, 1000000000, 1000000000], [1000000000, 1000000000], [0], [1])函数应返回 $[5000000000]$。
子任务
对于所有输入数据，满足：
- $1 \leq N, M \leq 150000$
- $1 \leq Q \leq 500000$
- 对于所有 $0 \leq i \leq N-1$，$1 \leq A[i] \leq 10^{9}$
- 对于所有 $0 \leq j \leq M-1$，$1 \leq B[j] \leq 10^{9}$
- 对于所有 $0 \leq k \leq Q-1$，$0 \leq L[k] \leq R[k] \leq M-1$
详细子任务附加限制及分值如下表所示。
| 子任务 | 分值 | 附加限制 |
|---|---|---|
| $1$ | $10$ | $N, M, Q \leq 3000$ |
| $2$ | $8$ | $Q \leq 300$ |
| $3$ | $20$ | 对于所有 $0 \leq k \leq Q-1$，$L[k] = 0$ 或 $B[L[k]-1] < \min(B[L[k]], B[L[k]+1], \ldots, B[R[k]])$；对于所有 $0 \leq k \leq Q-1$，$R[k] = M-1$ 或 $B[R[k]+1] < \min(B[L[k]], B[L[k]+1], \ldots, B[R[k]])$ |
| $4$ | $6$ | 对于所有 $0 \leq i \leq N-1$，$A[i] \leq 50$；对于所有 $0 \leq j \leq M-1$，$B[j] \leq 50$ |
| $5$ | $14$ | 对于所有 $0 \leq i \leq N-1$，$A[i]$ 恒定不变 |
| $6$ | $11$ | 对于所有 $0 \leq j \leq M-2$，$B[j] \geq B[j+1]$ |
| $7$ | $13$ | 对于所有 $0 \leq k \leq Q-1$，$L[k] = 0$ |
| $8$ | $7$ | 对于所有 $0 \leq k \leq Q-1$，$R[k] - L[k]$ 相同 |
| $9$ | $11$ | 无附加限制 |
样例交互库
示例评测程序接收以下格式的输入：
- 第 $1$ 行：$N\ M\ Q$
- 第 $2$ 行：$A[0]\ A[1]\ \ldots\ A[N-1]$
- 第 $3$ 行：$B[0]\ B[1]\ \ldots\ B[M-1]$
- 第 $4+k$ $(0 \leq k \leq Q-1)$ 行：$L[k]\ R[k]$
输出格式如下：
- 第 $1+k$ $(0 \leq k \leq Q-1)$ 行：设
max_stability返回值为 $C$，则输出 $C[k]$
请注意，示例评测程序可能与实际评测程序有所不同。