#include<bits/stdc++.h>

using namespace std;
using E=long long;

int main(){

#ifdef zzafanti
  freopen("in.in","r",stdin);
#endif // zzafanti

  cin.tie(nullptr),cout.tie(nullptr)->sync_with_stdio(false);

  int n,Q;
  cin>>n>>Q;

  vector<int> a(n+1),nxt(n+1),lst(n+1,n+1);

  unordered_set<int> st;
  for(int i=1; i<=n; i++){
    cin>>a[i];
    st.insert(a[i]);
  }
  int K=(int)(__lg(n))-4; K=max(K,2);
  if(st.size()<=3u) K+=4;
  vector<vector<int>> fa(n+2,vector<int>(K));
  vector<int> dep(n+2);
  for(int i=0; i<K; i++) fa[n+1][i]=n+1;

  int now=n;
  dep[n+1]=0;
  for(int i=n; i; i--){
    nxt[i]=lst[a[i]];
    if(nxt[i]<nxt[now]){
      now=i;
    }
    lst[a[i]]=i;
    fa[i][0]=nxt[now];
    dep[i]=dep[fa[i][0]]+1;
  }

  for(int j=1; j<K; j++){
    for(int i=1; i<=n; i++){
      fa[i][j]=fa[fa[i][j-1]][j-1];
    }
  }

  while(Q--){
    int l,r;
    cin>>l>>r;
    if(l>r) swap(l,r);
    int ans=2*(r-l);
    for(int i=K-1; ~i; i--){
      if(fa[l][i]<=r){
        l=fa[l][i];
        ans-=(1<<i);
      }
    }
    cout<<ans<<'\n';
  }

  return 0;
}