这东西在线不太能做，考虑离线扫描。扫描右端点 \(r\)，我们对每个位置 \(l\) 维护一个 \(p_l\) 表示最小的 \(p\) 使得 \([l,p]\) 是 \([l,r]\) 的合法子区间。
考虑如何维护 \(p_l\)。考虑新加入的右端点 \(r\)，加入一个数 \(a_r\)，上一次出现的位置为 \(lst_{a_r}=c\)，那么对于 \(c\) 和以前的位置是没有影响的；而 \((c,r]\) 这段区间由于没有 \(a_r\) 这个数，那么直接覆盖为 \(r\) 即可。可以用线段树维护。
考虑查询，当前扫描到 \(r\)，询问 \([l,r]\)。令 \(q_l\) 为最大的 \(q\) 使得 \([q,r]\) 合法，那么不难发现答案就是 \(\min\limits_{i\in[l,q_l]}\{p_i-i\}\)。这东西可以线段树上二分，但是多带了一半常数，估计过不去。
有一个很妙的并查集做法，学会了。
就是要对每个 \(l\) 维护 \(q_l\)，当插入 \(r\) 前已经有一个 \(lst_{a_r}\) 了，那么直接将 \(q_{lst_{a_r}}\to lst_{a_r}+1\) 即可。因为 \(q_l\) 相当于 \([l,r]\) 所有出现过的数的 \(lst\) 取 \(\min\)， \(lst_{a_r}\) 这个位置可以替换成 \(r\) 了，所以直接求 \(q_{lst_{a_r}+1}\) 即可。
upd : 写完了，竟然是最优解前三。
const int maxn = 2e6 + 200;
const int inf = 1e9;
struct seg { int mn, co; seg () { mn = inf, co = -1; } } tr[maxn << 2];
int n, m, a[maxn], lst[maxn], ans[maxn], fa[maxn];
tu3 q[maxn];
int getf(int x) { return x == fa[x] ? x : fa[x] = getf(fa[x]); }
#define ls x << 1
#define rs x << 1 | 1
#define mid ((l + r) >> 1)
void pushup(int x) { tr[x].mn = min(tr[ls].mn, tr[rs].mn); }
void pushcov(int x, int l, int r, int c) { tr[x].co = c, tr[x].mn = c - r + 1; }
void pushdown(int x, int l, int r) {
if (tr[x].co == -1) return;
pushcov(ls, l, mid, tr[x].co);
pushcov(rs, mid + 1, r, tr[x].co);
tr[x].co = -1;
}
void update(int l, int r, int s, int t, int c, int x) {
if (s <= l && r <= t) return pushcov(x, l, r, c);
pushdown(x, l, r);
if (s <= mid) update(l, mid, s, t, c, ls);
if (t > mid) update(mid + 1, r, s, t, c, rs);
pushup(x);
}
int query(int l, int r, int s, int t, int x) {
if (s <= l && r <= t) return tr[x].mn;
pushdown(x, l, r);
int res = inf;
if (s <= mid) res = min(res, query(l, mid, s, t, ls));
if (t > mid) res = min(res, query(mid + 1, r, s, t, rs));
return res;
}
signed main() {
n = read();
for (int i = 1; i <= n; i++) a[i] = read(), fa[i] = i;
m = read();
for (int i = 1; i <= m; i++) {
int l = read(), r = read();
q[i] = mt(r, l, i);
}
sort(q + 1, q + m + 1);
for (int i = 1, p = 1; i <= m; i++) {
int l = get<1>(q[i]), r = get<0>(q[i]), id = get<2>(q[i]);
while (p <= r) {
update(1, n, lst[a[p]] + 1, p, p, 1);
if (lst[a[p]]) fa[lst[a[p]]] = lst[a[p]] + 1;
lst[a[p]] = p;
p++;
}
r = getf(l);
ans[id] = query(1, n, l, r, 1);
}
for (int i = 1; i <= m; i++)
write(ans[i]), puts("");
return 0;
}