\(a_l, a_{l + 1}, \ldots a_r\) 是好的当且仅当 \(\exists k \in [l, r - 1], \max\limits_{i = l}^k a_i < \min\limits_{i = k + 1}^r a_i\)，称此时的 \(k\) 为分割点。
对 \(r\) 扫描线，单调栈维护极长的一些区间 \([L_i, R_i]\) 使得 \(\min\limits_{j = L_i}^r a_j = \min\limits_{j = R_i}^r a_j\)。由 \(\max\) 的不减性可得以 \(L_i\) 为分割点一定不劣。
可以 ST 表 + 二分对每个 \(L_i\) 求出一个 \(b_i\) 使得 \(l\) 取 \([b_i, L_i - 1]\) 时，\([l, r]\) 以 \(L_i\) 为分割点是好的。
把 \([b_i, L_i - 1]\) 扔到树状数组上，如果对于一个询问的 \(l\) 有区间覆盖它就合法。
时间复杂度 \(O((n + q) \log n)\)。
code
// Problem: D. Split
// Contest: Codeforces - Codeforces Round 905 (Div. 1)
// URL: https://codeforces.com/contest/1887/problem/D
// Memory Limit: 256 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<int, int> pii;
const int maxn = 300100;
const int logn = 20;
int n, a[maxn], m, stk[maxn], top, f[maxn][logn], ans[maxn];
pii b[maxn];
vector<pii> vc[maxn];
namespace BIT {
int c[maxn];
inline void update(int x, int d) {
for (int i = x; i <= n; i += (i & (-i))) {
c[i] += d;
}
}
inline void update(int l, int r, int x) {
update(l, x);
update(r + 1, -x);
}
inline int query(int x) {
int res = 0;
for (int i = x; i; i -= (i & (-i))) {
res += c[i];
}
return res;
}
}
inline int qmax(int l, int r) {
int k = __lg(r - l + 1);
return max(f[l][k], f[r - (1 << k) + 1][k]);
}
void solve() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
f[i][0] = a[i];
}
scanf("%d", &m);
for (int i = 1, l, r; i <= m; ++i) {
scanf("%d%d", &l, &r);
vc[r].pb(l, 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]);
}
}
for (int i = 1; i <= n; ++i) {
while (top && a[stk[top]] > a[i]) {
BIT::update(b[top].fst, b[top].scd, -1);
--top;
}
int j = stk[top] + 1;
stk[++top] = i;
int l = 1, r = j - 1, pos = j;
while (l <= r) {
int mid = (l + r) >> 1;
if (qmax(mid, j - 1) < a[i]) {
pos = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
b[top] = mkp(pos, j - 1);
BIT::update(pos, j - 1, 1);
for (pii p : vc[i]) {
int l = p.fst, id = p.scd;
ans[id] = (BIT::query(l) ? 1 : 0);
}
}
for (int i = 1; i <= m; ++i) {
puts(ans[i] ? "Yes" : "No");
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}