题目链接：http://codeforces.com/contest/765/problem/F
题意概述：
给出一个序列，若干组询问，问给出下标区间中两数作差的最小绝对值。
分析：
这个题揭示着数据结构题目世界的真谛......
在线显然凉凉......考虑离线做法。
本题的主要思想：
首先考虑把所有的询问按照右端点排序，用一个指针扫整个序列，同时考虑i作为一组差的右端可以对右端点大于等于i的询问做出的贡献。我们可以发现，我们扫到当前点i，对于所有询问的右端点大于等于i的询问，如果其左端点小于等于i，那么i这个位置就可能对它们的答案做出贡献，换句话说我们只要考虑i作为差的右端可以对哪些左端的答案做出贡献，然后维护当前每个点作为左端的答案，查询的时候直接进行区间最小值的查询即可。
绝对值是麻烦的，因此我们简单一点，考虑所有j<i并且aj>=ai的贡献，然后倒着扫一遍就可以考虑剩下的可能贡献。
假设我们现在扫到位置i，左边有第一个大于ai的元素aj，我们贪心考虑，最终能够让 i作为下标较大的一方参与的答案变得更小 的j'满足：ai<=aj'<aj。但是这个性质显然还不够强，我们继续考虑，发现：
当aj'-ai>aj-aj'时，我们反向扫回来的时候，由于区间[j',j]一定被[j',i]包含，如果存在一个询问包括了[j',i]，那么也一定包括了[j',j]，显然这个时候aj-aj'是一个更加优秀的答案，aj'-ai更劣。
因此我们找到的j'一定要满足：aj'-ai<=aj-aj' -> 2aj'<=ai+aj，也就是说我们最多找到O(log(ai+a_first_j))个可以对i作为右端点的答案产生贡献的位置。
因为我们将右端点排序，因此我们维护当前所有的点作为下标较小的一方参与的时候的答案，当我们遇到一个询问p的右端点pr=i的时候，只需要查询区间[pl,i]中的最小值即可。
最后倒着来一遍，得到最终的答案。
在log次查找的时候我们实质上找的是权值在[ai,(ai+aj)/2]范围中的小于j的最大下标，分析一下发现可以直接用一棵权值线段树维护，因为我们找的权值区间内的序列下标不可能大于j（不然的话我们在之前就应该找到它了）。
找到第一个j的时候可以直接在序列线段树中进行二分。
时间复杂度O(NlogNloga)
（PS：突然发现变量rank,hash在C++11下面编译不了是什么情况？！）
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<cctype>
#define inf (1e9+5)
using namespace std;
const int MAXN=;
const int MAXM=; int N,M,A[MAXN],Rank[MAXN],B[MAXN],ans[MAXM],tot;
struct data{
int l,r,id;
friend bool operator < (data x,data y){
return x.r<y.r;
}
}q[MAXM];
struct segment_tree{
static const int maxn=;
int rt,np,lc[maxn],rc[maxn],mx[maxn],mn[maxn];
void init(){ rt=np=; }
void pushup1(int now){ mn[now]=min(mn[lc[now]],mn[rc[now]]); }
void pushup2(int now){ mx[now]=max(mx[lc[now]],mx[rc[now]]); }
void build(int &now,int L,int R){
now=++np,lc[now]=rc[now]=,mx[now]=-,mn[now]=inf;
if(L==R) return;
int m=L+R>>;
build(lc[now],L,m);
build(rc[now],m+,R);
}
void update1(int now,int L,int R,int pos,int v){
if(L==R){ mn[now]=min(mn[now],v); return; }
int m=L+R>>;
if(pos<=m) update1(lc[now],L,m,pos,v);
else update1(rc[now],m+,R,pos,v);
pushup1(now);
}
void update2(int now,int L,int R,int pos,int v){
if(L==R){ mx[now]=max(mx[now],v); return; }
int m=L+R>>;
if(pos<=m) update2(lc[now],L,m,pos,v);
else update2(rc[now],m+,R,pos,v);
pushup2(now);
}
int query_p(int now,int L,int R,int v){
if(L==R) return mx[now]>=v?L:-;
int m=L+R>>;
if(mx[rc[now]]>=v) return query_p(rc[now],m+,R,v);
return query_p(lc[now],L,m,v);
}
int query_max(int now,int L,int R,int A,int B){
if(A<=L&&R<=B) return mx[now];
int m=L+R>>;
if(B<=m) return query_max(lc[now],L,m,A,B);
if(A>m) return query_max(rc[now],m+,R,A,B);
return max(query_max(lc[now],L,m,A,B),query_max(rc[now],m+,R,A,B));
}
int query_min(int now,int L,int R,int A,int B){
if(A<=L&&R<=B) return mn[now];
int m=L+R>>;
if(B<=m) return query_min(lc[now],L,m,A,B);
if(A>m) return query_min(rc[now],m+,R,A,B);
return min(query_min(lc[now],L,m,A,B),query_min(rc[now],m+,R,A,B));
}
}st1,st2; void data_in()
{
scanf("%d",&N);
for(int i=;i<=N;i++) scanf("%d",&A[i]);
scanf("%d",&M);
for(int i=;i<=M;i++){
scanf("%d%d",&q[i].l,&q[i].r);
q[i].id=i;
}
}
int id(int v){ return upper_bound(B+,B+tot+,v)-B-; }
void solve()
{
st1.init(); st2.init();
st1.build(st1.rt,,N); st2.build(st2.rt,,tot);
int p=;
st1.update2(st1.rt,,N,,A[]);
st2.update2(st2.rt,,tot,Rank[],);
for(int i=;i<=N;i++){
int j=st1.query_p(st1.rt,,N,A[i]);
if(j!=-){
st1.update1(st1.rt,,N,j,A[j]-A[i]);
while((j=st2.query_max(st2.rt,,tot,Rank[i],id((A[i]+A[j])/)))!=-){
st1.update1(st1.rt,,N,j,A[j]-A[i]);
if(A[j]-A[i]==) break;
}
}
while(p<=M&&q[p].r<=i){
ans[q[p].id]=min(ans[q[p].id],st1.query_min(st1.rt,,N,q[p].l,q[p].r));
p++;
}
if(p>M) break;
st1.update2(st1.rt,,N,i,A[i]);
st2.update2(st2.rt,,tot,Rank[i],i);
}
}
void work()
{
memcpy(B,A,sizeof(A));
sort(B+,B+N+);
tot=unique(B+,B+N+)-B-; for(int i=;i<=N;i++) Rank[i]=lower_bound(B+,B+tot+,A[i])-B;
for(int i=;i<=M;i++) ans[i]=inf;
sort(q+,q+M+);
solve(); int l=,r=N;
while(l<r) swap(Rank[l],Rank[r]),swap(A[l++],A[r--]);
for(int i=;i<=M;i++){
swap(q[i].l,q[i].r);
q[i].l=N-q[i].l+,q[i].r=N-q[i].r+;
}
sort(q+,q+M+);
solve(); for(int i=;i<=M;i++) printf("%d\n",ans);
}
int main()
{
data_in();
work();
return ;
}