题意

假设所有查询的右边界 $r$ 都相同。那么对于该查询，答案可以是某个整数 $i$，使得 $i$ 在数组前缀 $[1, r]$ 中的最后一次出现位于查询区间内，而它的倒数第二次出现位于区间外（或者根本不存在）。更正式地，定义 $f(i)$ 为满足 $j < i$ 且 $a_j = a_i$ 的最大下标 $j$（若不存在则为 $-1$）。查询的答案是某个数 $a_k$，满足 $l \le k \le r$ 且 $f(k) < l$（并且 $k$ 是 $a_k$ 在区间 $[1, r]$ 中的最右出现位置）。对于固定的右边界 $r$，我们可以构建一棵线段树，对于每个下标 $x$（$x$ 是 $a_x$ 在 $[1, r]$ 中的最右出现位置），存储 $f(x)$ 的值；如果我们在该树中查询区间 $[l, r]$ 上的最小值，就可以尝试找到答案。设最小值的位置为 $m$。如果 $f(m) < l$，那么 $a_m$ 可以作为答案；否则没有答案。

思路

但这种方法太慢，因为我们无法为每个可能的 $r$ 都构建一棵线段树。有两种方法可以解决这个问题：你可以按右边界对所有查询排序，并在移动右边界时维护线段树（当从 $r$ 移动到 $r+1$ 时，我们需要更新位置 $f(r+1)$ 和 $r+1$ 上的值），或者使用可持久化线段树来获得在线解法。

算法步骤

1. 对于每个位置 $i$，预处理 $f(i)$，即上一个与 $a_i$ 相同的位置（若不存在则为 $-1$）。
2. 方法一（离线）：
   • 将所有查询按右边界 $r$ 排序。
   • 从左到右扫描数组，维护一棵线段树，其中位置 $x$ 存储 $f(x)$（仅当 $x$ 是当前 $a_x$ 的最右出现位置时）。
   • 当右边界从 $r$ 移动到 $r+1$ 时，更新位置 $f(r+1)$ 和 $r+1$ 上的值。
   • 对于每个查询 $[l, r]$，在线段树上查询区间 $[l, r]$ 的最小值及其位置 $m$。若 $f(m) < l$，则答案为 $a_m$；否则无答案。
3. 方法二（在线）：
   • 使用可持久化线段树，为每个右边界 $r$ 保存一个版本。
   • 查询时直接使用对应 $r$ 的版本进行区间最小值查询。

复杂度分析

• 方法一（离线排序 + 线段树）：时间复杂度 $O((n + q) \log n)$，空间复杂度 $O(n)$。
• 方法二（可持久化线段树）：时间复杂度 $O((n + q) \log n)$，空间复杂度 $O(n \log n)$。
• 使用 Mo 算法（带优化）的最坏情况复杂度为 $O((n + q) \sqrt{n})$，但需要额外优化才能通过时间限制。

代码说明

我们尝试淘汰使用 Mo 算法的解法，但实际上某些实现可以通过优化在时间限制内运行。这里有两个可能有效的优化：将元素分块时，第一块按右边界升序排序，第二块按降序排序，第三块再按升序排序，以此类推。此外，还可以通过使用 sqrt 分解来维护可能的答案集合，从而得到基于 Mo 的解法，其最坏情况复杂度为 $O((n + q) \sqrt{n})$。

#pragma GCC optimize (3)
#pragma GCC optimize ("Ofast")
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#define N 500007
#define reg register
using namespace std;

struct query{
	int l,r,id;
}q[N];

int a[N],cnt[N],pos[N],be[N];
int stk[N],ans[N];
int n,m,top,unit;

inline void read(int &x);
void print(int x);
inline bool cmp(query x,query y);
inline void add(int t);
inline void del(int t);
inline char gc();

int main(){
	reg int l,r;
	read(n);
	unit = sqrt(n);
	for(reg int i=1;i<=n;++i){
        read(a[i]);
        be[i] = i/unit+1;
    }
	read(m);
	for(reg int i=1;i<=m;++i){
		read(q[i].l),read(q[i].r);
		q[i].id = i;
	}
	sort(q+1,q+1+m,cmp);
	l = r = 1;
	add(a[1]);
	for(reg int i=1;i<=m;++i){
		while(r<q[i].r) add(a[++r]);
		while(r>q[i].r) del(a[r--]);
		while(l<q[i].l) del(a[l++]);
		while(l>q[i].l) add(a[--l]);
		ans[q[i].id] = stk[top];
	}
	for(reg int i=1;i<=m;++i){
		print(ans[i]);
		putchar('\n');
	}
	return 0;
} 

inline char gc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}

inline void add(int t){
    ++cnt[t];
	if(cnt[t]==1){
		stk[++top] = t; //放到栈顶
		pos[t] = top; //更新栈顶元素所在位置
	}else if(cnt[t]==2){
		stk[pos[t]] = stk[top]; //栈顶元素替换t的位置
		pos[stk[top]] = pos[t]; //把位置更新一下
		stk[top--] = pos[t] = 0; //原来的地方要清0
	}
}

inline void del(int t){
    --cnt[t];
	if(cnt[t]==1){
		stk[++top] = t;
		pos[t] = top;
	}else if(!cnt[t]){
		stk[pos[t]] = stk[top];
		pos[stk[top]] = pos[t];
		stk[top--] = pos[t] = 0;
	}
}

inline bool cmp(query a,query b){ 
    return (be[a.l]^be[b.l])?a.l<b.l:((be[a.l]&1)?a.r<b.r:a.r>b.r); //传说中的奇偶排序优化
}

inline void read(int &x){
	x = 0;
	char c = gc();
	while(c<'0'||c>'9') c = gc();
	while(c>='0'&&c<='9'){
		x = (x<<3)+(x<<1)+(c^48);
		c = gc();
	}
} 

void print(int x){
	if(x>9) print(x/10);
	putchar(x%10+'0');
}