静态区间有关最值问题，离线、单调栈、数据结构（通常是线段树）维护是十分套路的，本题思路十分好想，码量算不上巨大，并且其他类似的题目都是紫，所以申请降紫。

先放出暴力代码：

#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;

const int N = 500010;

int n, m, val[N], ans[N];
vector<pair<int, int>> qry[N];

int mi[N], mx[N];

struct Bit_Tree {
    constexpr inline int lowbit(int x) {
        return x & -x;
    }
    int tree[N];
    void modify(int p, int v) {
        for (int i = p; i; i -= lowbit(i))
            tree[i] = max(tree[i], v);
    }
    int query(int p) {
        int res = 0;
        for (int i = p; i <= n; i += lowbit(i))
            res = max(res, tree[i]);
        return res;
    }
} yzh;

signed main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &val[i]);
        mi[i] = mx[i] = val[i];
    }
    scanf("%d", &m);
    for (int l, r, i = 1; i <= m; ++i) {
        scanf("%d%d", &l, &r);
        qry[r].push_back({l, i});
        ans[i] = 1;
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = i; j >= 1; --j) {
            mi[j] = min(mi[j], val[i]);
            mx[j] = max(mx[j], val[i]);
            if (mi[j] < val[i] && mx[j] > val[i]) break;  // there
            if ((mi[j] == val[j] && mx[j] == val[i]) ||
                (mx[j] == val[j] && mi[j] == val[i])) {
                    yzh.modify(j, i - j + 1);
                }
        }
        for (auto& [l, idx]: qry[i]) {
            ans[idx] = yzh.query(l);
        }
    }
    for (int i = 1; i <= m; ++i) printf("%d\n", ans[i]);
    return 0;
}

显然，时间复杂度是 $\Theta(n^2\log n)$ 的，但是加上标记处的剪枝水过去了，甚至是最优解。Hack 也很好搞：

#include <cstdio>
#include <iostream>
using namespace std;

int n = 500000;

signed main() {
    freopen("yzh", "w", stdout);
    cout << n << endl;
    for (int i = 1; i <= n; ++i) cout << 1 << " \n"[i == n];
    cout << n << endl;
    for (int i = 1; i <= n; ++i) cout << 1 << ' ' << n << endl;
    return 0;
}

所以申请降紫 & 加强数据。