我們考慮這道題目要求我們在數列 \(s\) 中找到一個一個區間 \([i,j]\) 滿足：

• \(l\in[1,l-1],r\in [r+1,n]\)
• \(j-i+1\) 最小化
• 在數列 \(s\) 中找不到一個與區間 \([i,j]\) 不同的區間 \([p,q]\) (即 \(i\ne p,j\ne q\) )滿足 \(s_i=s_p,s_j=s_q\)
• \(s_i\ne s_j\)

我們不難發現后面兩個條件可以轉化為區間 \([i,j]\) 滿足：

• \(\forall p\in [i,j-1]\cup [j+1,n] ,s_j\ne s_p\)
• \(\forall q\in [1,i-1]\cup [i+1,j] ,s_i\ne s_q\)

我們不妨在遍歷 \(j\) 的同時用一個 set 來維護所有的 \(s_i\) ，滿足 \(s_i\) 在 \(s_1\) 到 \(s_j\) 中僅出一次，再用桶維護從最接近 \(l\) 并且滿足上述條件的 \(i\) 開始一直到 \(n\)，數列 \(s\) 里每個數出現的次數，如果當前的 \(s_j\) 出現次數為1，那么這就最佳答案，直接輸出，如果遍歷完所有 \(j\) 但沒有一個 \(j\) 滿足上述條件，則不存在一個合法方案，輸出 -1。

CODE

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
int n,l,r,s[1000005],book[1000005],id[1000005],cnt[1000005];
set<pair<int,int> > q;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>l>>r;
	for(int i=1;i<=n;i++)
		cin>>s[i];
	for(int i=1;i<l;i++){
		book[s[i]]++;
		if(book[s[i]]==1){
			id[s[i]]=i;
			q.insert({l-i,s[i]}); 
		}
		else if(book[s[i]]==2){
			auto it=q.find({l-id[s[i]],s[i]});
			q.erase(it);
		}
	}
	for(int i=l;i<=r;i++){
		book[s[i]]++;
		if(book[s[i]]==2&&id[s[i]]){
			auto it=q.find({l-id[s[i]],s[i]});
			q.erase(it);
		}
	}
	auto it=q.begin();
	pair<int,int> ttt=*it;
	for(int i=n;i>=l-ttt.fi;i--)
		cnt[s[i]]++;
	for(int i=r+1;i<=n;i++){
		book[s[i]]++;
		if(book[s[i]]==2&&id[s[i]]){
			auto it=q.find({l-id[s[i]],s[i]});
			pair<int,int> ttt=*it;
			q.erase(it);
			auto iti=q.begin();
			pair<int,int> kkk=*iti;
			for(int j=l-kkk.fi;j<l-ttt.fi;j++)
				cnt[s[j]]++; 
		}
		if(cnt[s[i]]==1){
			auto it=q.begin();
			if(it==q.end())
				continue;
			pair<int,int> ttt=*it;
			cout<<(i-l+ttt.fi+1);
			return 0;
		}
	}
	cout<<-1;
	return 0;
}