好的，我将这道题整理为清晰的题面格式，并补充样例解释、数据范围与时空限制：

题目描述

原题来自：Vijos P1512

从前有个人名叫 W and N and B，他有着天才般的记忆力，他珍藏了许多许多的宝藏。在他离世之后留给后人一个难题（专门考验记忆力的啊！），如果谁能轻松回答出这个问题，便可以继承他的宝藏。

题目是这样的：给你一大串数字（编号为 $1$ 到 $N$，大小可不一定哦！），在你看过一遍之后，它便消失在你面前，随后问题就出现了，给你 $M$ 个询问，每次询问就给你两个数字 $A,B$，要求你瞬间就说出属于 $A$ 到 $B$ 这段区间内的最大数。

一天，一位美丽的姐姐从天上飞过，看到这个问题，感到很有意思（主要是据说那个宝藏里面藏着一种美容水，喝了可以让这美丽的姐姐更加迷人），于是她就竭尽全力想解决这个问题。BUT，她每次都以失败告终，因为这数字的个数是在太多了！于是她请天才的你帮他解决。如果你帮她解决了这个问题，可是会得到很多甜头的哦！

输入格式

• 第一行一个整数 $N$ 表示数字的个数；
• 第二行为 $N$ 个整数；
• 第三行一个整数 $M$，表示提问的次数；
• 接下来 $M$ 行，每行两个整数 $A,B$，表示询问区间 $[A,B]$ 的最大值。

输出格式

输出共 $M$ 行，每行输出一个整数，表示对一个询问的回答。

样例

样例输入

6
34 1 8 123 3 2
4
1 2
1 5
3 4
2 3

样例输出

34
123
123
8

样例说明

数列：$[34, 1, 8, 123, 3, 2]$。

询问1：$[1,2]$ → $34, 1$，最大值 $34$。
询问2：$[1,5]$ → $34, 1, 8, 123, 3$，最大值 $123$。
询问3：$[3,4]$ → $8, 123$，最大值 $123$。
询问4：$[2,3]$ → $1, 8$，最大值 $8$。

数据范围

• 对于 $30\%$ 的数据，$1 \le N \le 10^4, 1 \le M \le 100$；
• 对于 $100\%$ 的数据，$1 \le N \le 2\times 10^5, 1 \le M \le 10^4$。

时空限制

• 时间：$1000 \text{ ms}$
• 内存：$524288 \text{ KB}$（512 MB）

提示
此题为 静态区间最大值查询（RMQ） 问题。

由于 $N$ 较大（$2\times 10^5$），$M$ 较小（$10^4$），可以使用 ST表（Sparse Table） 实现 $O(1)$ 查询，预处理 $O(N \log N)$，总复杂度 $O(N \log N + M)$，比线段树 $O(M \log N)$ 更优。

ST表实现步骤：

1. 预处理 $\log_2$ 表（或使用 __lg 函数）；
2. 设 $f[i][j]$ 表示区间 $[i, i+2^j-1]$ 的最大值；
3. 初始化 $f[i][0] = a[i]$；
4. 递推：$f[i][j] = \max(f[i][j-1], f[i+2^{j-1}][j-1])$；
5. 查询 $[l, r]$：令 $k = \lfloor \log_2(r-l+1) \rfloor$，返回 $\max(f[l][k], f[r-2^k+1][k])$。

复杂度：

• 预处理：$O(N \log N)$
• 每次查询：$O(1)$

注意：

• $N$ 最大 $2\times 10^5$，$\log_2 N \approx 18$，ST表大小 $N \times 19$ 约 $3.8\times 10^6$ 个整数，内存约 $15$ MB，可以接受；
• 输入输出建议使用 scanf/printf 或关闭同步的 cin/cout。

代码框架：

int f[N][20]; // f[i][j] 表示区间 [i, i+2^j-1] 的最大值
int log2[N];  // 预处理 log2 值

// 预处理
for (int i = 2; i <= N; i++) log2[i] = log2[i>>1] + 1;
for (int i = 1; i <= N; i++) f[i][0] = a[i];
for (int j = 1; (1<<j) <= N; j++)
    for (int i = 1; i + (1<<j) - 1 <= N; i++)
        f[i][j] = max(f[i][j-1], f[i+(1<<(j-1))][j-1]);

// 查询
int query(int l, int r) {
    int k = log2[r-l+1];
    return max(f[l][k], f[r-(1<<k)+1][k]);
}