***D. Closest Equals( OFF LINE SEGMENT TREE)

D. Closest Equals

You are given sequence a1, a2, ..., an and m queries lj, rj (1 ≤ lj ≤ rj ≤ n). For each query you need to print the minimum distance between such pair of elements ax and ay (x ≠ y), that:

• both indexes of the elements lie within range [lj, rj], that is, lj ≤ x, y ≤ rj;
• the values of the elements are equal, that is ax = ay.

The text above understands distance as |x - y|.

Input

The first line of the input contains a pair of integers n, m (1 ≤ n, m ≤ 5·105) — the length of the sequence and the number of queries, correspondingly.

The second line contains the sequence of integers a1, a2, ..., an ( - 109 ≤ ai ≤ 109).

Next m lines contain the queries, one per line. Each query is given by a pair of numbers lj, rj (1 ≤ lj ≤ rj ≤ n) — the indexes of the query range limits.

Output

Print m integers — the answers to each query. If there is no valid match for some query, please print -1 as an answer to this query.

Examples

input

5 3
1 1 2 3 2
1 5
2 4
3 5

output

1
-1
2

input

6 5
1 2 1 3 2 3
4 6
1 3
2 5
2 4
1 6

output

2
2
3
-1
2

-------------------------------------------------------EDITORIAL-------------------------------------------------

OFF LINE SEGMENT TREE

this problem can be solved in a very tricky  way with the help of segment tree ..

 in the offline seg tree we  will first of all sort  queries with the given array 

first of all we will sort the numbers with the queries right value , 

sorting paramiter will be the position of the right of query and the position of the elements, 

so that when we cover  any query its all possible ranges must  which can cover in that query must 

be processed earlier 

now  when we are using any number that we find its last occur and closest of this number will be that number  and update segment tree of its last occurance position not its possition since in some query its last occurance may be not covered so if we update and at its index it will give wrong answer 

nor if we  covere any query than just find min of its l to r range , 

------------------------------------------------------code-----------------------------------------------------------

#include<bits/stdc++.h>

using namespace std;

typedef long long int lli;

map<lli,int> ma;

int ans[1000000];

#define infi 10000000

struct st

 {

  lli num;

  int  type;// 0 means number , 1 means query

  int  lft;// left and right are for querry for num left=fright = index 

  int rigth;

  int ans;

 }  arr[7000000];

 

 int seg[7000000];

 

 void update(int idx,int start,int end,int ups,int upe,int val)

  {

   //cout<<" upd "<<start<<" "<<end<<endl;

   if(start>end  || start>upe || end< ups)

 {

     return ;

 }

  else if(start==end && ups==start)

     {

 

  seg[idx]=val;   

  return ;

}

int mid=(start+end)/2;

update(2*idx,start,mid,ups,upe,val);

update(2*idx+1,mid+1,end,ups,upe,val);

seg[idx]=min(seg[2*idx],seg[2*idx+1]);

  }

  

  int qry(int idx,int start,int end,int qs,int qe)

   {

    if(start>end  || start>qe || end<qs)

 {

     return INT_MAX ;

 }

    else if(start>=qs && end<=qe)

    return seg[idx];

    int mid=(start+end)/2;

    int q1=qry(2*idx,start,mid,qs,qe);

    int q2=qry(2*idx+1,mid+1,end,qs,qe);

    return min(q1,q2);

   

   }

 

 

  

  bool comp(st &qq,st &bb)

   { 

          if(qq.rigth< bb.rigth)

          return 1;

          else if(qq.rigth==bb.rigth)

          return qq.type<bb.type;

          return 0;

  }

  

int main()

{

  int n,m;

 cin>>n>>m;

  for(int i=0;i<7000000;i++) seg[i]=infi;

 for(int i=0;i<n;i++)

     {

     

        lli a;

       scanf("%lld",&a);

       arr[i].lft=i;

       arr[i].rigth=i;

       arr[i].num=a;

       arr[i].type=0;

       arr[i].ans=-1;

       ma[a]=-1;

        

}

 

for(int j=0;j<m;j++)

 {

   int l,r;

   scanf("%d %d",&l,&r);

   l--;

   r--;

   

   arr[n+j].lft=l;

   arr[n+j].rigth=r;

   arr[n+j].type=1;

   arr[n+j].num=j;// for query num will contain the index of the  query..

   arr[n+j].ans=-1;

 }

 int al=n+m;

 

sort(arr,arr+al,comp);

int ext=0;

for(int i=0;i<n+m;i++)

{

int type=arr[i].type;

// cout<<" type "<<type<<endl;

if(type==0)

 {

   

    lli num=arr[i].num;

    

  int last=ma[num];

  // cout<<"using  "<<num <<" its last "<<last<<endl;

  if(last!=-1)

      {

      //cout<<" update "<<num<<" its last occ is at dist "<<i-last-ext<<endl;

      update(1,0,n+m-1,last,last,i-last-ext);

}

ma[num]=i-ext;

  }

  

  else

  {

  ext++;

  int l=arr[i].lft;

  int r=arr[i].rigth;

  // cout<<" dealing with query "<<l<<" "<<r<<endl;

  int an=qry(1,0,n+m-1,l,r);

 // cout<<" ans of this query is "<<ans<<endl;

  if(an!=infi)

  ans[arr[i].num]=an;

  else ans[arr[i].num]=-1;

  }

}

for(int i=0;i<m;i++)

 {

  cout<<ans[i]<<" ";

 }

}