现在有一个序列 a1, a2, ..., ana1, a2, ..., an ，还有m个查询 lj, rj (1 ≤ lj ≤ rj ≤ n)lj, rj (1 ≤ lj ≤ rj ≤ n) 。对于每一个查询，请找出距离最近的两个元素 axax 和 ay (x ≠ y)ay (x ≠ y) ，并且满足以下条件：
? lj ≤ x, y ≤ rj;lj ≤ x, y ≤ rj;
? ax = ay。ax = ay。
两个数字的距离是他们下标之差的绝对值 |x ? y||x ? y| 。
Input
单组测试数据。
第一行有两个整数n, m (1≤n,m≤5*10^5)，表示序列的长度和查询的次数。
第二行有n个整数a1,a2,...,an (-10^9≤ai≤10^9)。
接下来有m行，每一行给出两个整数lj,rj (1≤lj≤rj≤n)表示一个查询。
Output
对于每一个查询，输出最近的距离，如果没有相等的元素，输出-1。
Sample Input
样例输入1
5 3
1 1 2 3 2
1 5
2 4
3 5Sample Output
样例输出1
1
-1
2题解：线段树维护区间最小值，区间查询即可。固定一个右端点，然后把他能带来的最小值更新，区间查询即可。
线段树维护的是1到它上一次出现位置的最小值。仔细想想这样维护！！！
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<cmath>
#include<set>
#include<map>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define lson i<<1,l,m
#define rson i<<1|1,m+1,r
#define oo cout<<"!!!"<<endl;
typedef long long ll;
typedef unsigned long long ull;
#define ms(s) memset(s, 0, sizeof(s))
const int inf = 1e7;
//headconst int maxn = 1e6+11111;
int minv[maxn<<1],lazy[maxn<<1];
void pushup(int i)
{minv[i] = min(minv[i<<1],minv[i<<1|1]);
}
void pushdown(int i,int l,int r)
{if(lazy[i]!=inf){minv[i<<1] = min(minv[i<<1],lazy[i]);minv[i<<1|1] = min(minv[i<<1|1],lazy[i]);lazy[i<<1] = min(lazy[i<<1],lazy[i]);lazy[i<<1|1] = min(lazy[i<<1|1],lazy[i]);lazy[i] = inf;}
}void build(int i,int l,int r)
{minv[i] = lazy[i] = inf;if(l==r)return;int m = (l+r)>>1;build(lson);build(rson);
}void update(int i,int l,int r,int ql,int qr,int v)
{if(ql<=l && qr>=r){minv[i] = min(minv[i],v);lazy[i] = min(lazy[i],v);return;}pushdown(i,l,r);int m = (l+r)>>1;if(ql<=m)update(lson,ql,qr,v);if(qr>m)update(rson,ql,qr,v);pushup(i);
}int query(int i,int l,int r,int ql,int qr)
{if(ql<=l && qr>=r)return minv[i];pushdown(i,l,r);int ans = inf;int m = (l+r)>>1;if(ql<=m)ans = min(ans,query(lson,ql,qr));if(qr>m)ans = min(ans,query(rson,ql,qr));pushup(i);return ans;
}
struct node
{int v,id;bool operator < (const node& o)const{return v < o.v;}
}a[maxn];
struct node1
{int l,r,id;bool operator < (const node1& o)const{return r < o.r;}
}ans[maxn];
int res[maxn];
int pre[maxn],b[maxn],d[maxn];int read(){int sum=0,p=1;char c=getchar();while (c<'0'||c>'9') {if (c=='-') p=-p;c=getchar(); }while (c>='0'&&c<='9'){sum=sum*10+c-'0';c=getchar();};;;return sum*p;
}
inline void write(int x){if (x<0) putchar('-'),x=-x;if (x>=10) write(x/10);putchar('0'+x%10);
}int main()
{int n,m;cin>>n>>m;rep(i,1,n+1){a[i].v = read();a[i].id = i;}rep(i,1,m+1){ans[i].l = read();ans[i].r = read();ans[i].id = i;}sort(a+1,a+1+n);sort(ans+1,ans+1+m);int cnt = 1;b[a[1].id] = 1;rep(i,2,n+1){if(a[i].v == a[i-1].v)b[a[i].id] = b[a[i-1].id];else b[a[i].id] = ++cnt;}memset(d,-1,sizeof d);rep(i,1,n+1){if(d[b[i]]!=-1){pre[i] = d[b[i]];d[b[i]] = i;}else d[b[i]] = i;}build(1,1,n);for(int i=1,j=1;i<=n,j<=m;i++){if(pre[i])update(1,1,n,1,pre[i],i-pre[i]);while(j<=m && i == ans[j].r){res[ans[j].id] = query(1,1,n,ans[j].l,ans[j].r);//固定右端点j++;}}rep(i,1,m+1){if(res[i] == inf)puts("-1");else write(res[i]),puts("");}return 0;
}