*3500。把我吓到了，其实这题比较水，已经快做出来了。
顺便一提 CF 怎么这么喜欢出 ST 表。
二元组不好看，换成 \(f: \text{Interval} \to \text{Interval}\)（
首先对于同一个 \(l\)，区间随右端点增大单调不减。但是这个好像没什么用。
然后观察可以发现这个 \(f([l,r]) = f([l,x_1]) \bigcup f([x_1+1,x_2])\bigcup \dotsb \bigcup f([x_k+1,r])\)，其中 \(x_i \lt x_{i+1},x_i \in [l,r]\)。
也就是随便戳若干断点，分割出的区间的函数并就是整个区间的函数。
其实这是一个更强的结论：若干区间并的函数值等于这些区间函数值的并。
（这里有个条件的，就是这些区间相邻的两个 \(x,y\) 要有交或者 \(r_x = l_y-1\)）
考虑这个有什么用，可以写 ST 表做到 \(O(n \log n) \sim O(1)\) 查询一个区间的 \(f\)，然后好像不太会了 /ng。
妈的，差一点就想出来了 /fn /fn /fn
应该给自己留更多思考时间的。现在浑身难受。
现在我们抓着 ST 表继续搞。那么我们使用以上结论，设 ST 表划分的区间是 \([l,k_1]\) 和 \([k_2,r]\)，则 \(f([l,r]) = f([l,k_1]) \bigcup f([k_2,r])\)。
考虑证明 \(f^2([l,r]) = f^2([l,k_1]) \bigcup f^2([k_2,r])\)。
证明：\(f^2([l,r]) = f(f([l,k_1]) \bigcup f([k_2,r]))\)，再次使用结论，\(\text{RHS} = f(f([l,k_1])) \bigcup f(f([k_2,r])) = f^2([l,k_1]) \bigcup f^2([k_2,r])\)，得证。
Upd：关于这里可以再次使用结论有一个条件就是 \(f([l,k_1]) \bigcap f([k_2,r])\) 不为空，由于是 ST 表所以 \(l \lt k_2 \le k_1 \lt r\)，那么这两个区间有交，两个区间的函数值也一定有交（包含相同元素，这些相同元素一定被包括在函数值这个区间里）。
归纳可知 \(f^k([l,r]) = f^k([l,k_1]) \bigcup f^k([k_2,r])\)。
那么就可以魔改一下 ST 表了，我们在前面再加一维 \(k\) 表示这个 ST 表存的是 \(f^{2^k}([l,r])\)，然后每次直接做就行了。时间复杂度 \(O(n \log^2 n + q \log n)\)，空间复杂度 \(O(n \log^2 n)\)，由于这是 CF，而且给了 1G，所以你就 Happy New Year 了。
启发性大概在于这种不好搞的函数尝试分拆、组合来观察可并性，或者找单调性，然后利用这些性质套上数据结构维护；还有就是做若干次给定变换可以考虑倍增。
Upd：Happy New Year 了。
#include <bits/stdc++.h>
using namespace std;
#define ri register int
#define ll long long
#define Tp template<class T>
namespace SlowIO{
const int End=1e6; static char outp[End],buf[End],*p1=buf,*p2=buf; inline char gchar(){ return p1==p2&&(p2=(p1=buf)+fread(buf,1,End,stdin),p1==p2)?EOF:*p1++; }
Tp inline void rd(T &x,char i=gchar(),bool f=0){ x=0; while(i<48||i>57) f|=i=='-',i=gchar(); while(i>=48&&i<=57) x=(x<<3)+(x<<1)+(i^48),i=gchar(); f&&(x=-x); } Tp inline void op(T x,int out=0){ if(!x){ putchar(48); return; } x<0&&(x=-x,putchar('-')); while(x) outp[++out]=(x%10)^48,x/=10; while(out) putchar(outp[out--]); } Tp inline void writeln(T x){ op(x),putchar('\n'); } Tp inline void writesp(T x){ op(x),putchar(' '); } Tp inline void write(T x,char c=0){ op(x); c&&putchar(c); }
}; using namespace SlowIO;
const int N = 100003;
int n,q,a[N],Log2[N];
struct Data{ int l,r; inline Data operator +(const Data &a){ return {min(l,a.l),max(r,a.r)}; } }st[18][18][N];
auto Chk = [](Data x){ return x.l==1&&x.r==n; };
auto Qry = [](int i,int l,int r){ int k = Log2[r-l+1]; return st[i][k][l]+st[i][k][r-(1<<k)+1]; };
main(){
rd(n),rd(q); bool f1=0,f2=0;
for(int i=1;i<=n;++i) rd(a[i]),st[0][0][i]={a[i],a[i]},f1|=a[i]==1,f2|=a[i]==n;
for(int i=2;i<=n;++i) Log2[i]=Log2[i>>1]+1;
for(int i=n;i>=1;--i)
for(int j=1;i+(1<<j)-1<=n;++j)
st[0][j][i]=st[0][j-1][i]+st[0][j-1][i+(1<<j-1)];
for(int k=1;k<18;++k)
for(int i=n;i>=1;--i)
for(int j=1;i+(1<<j)-1<=n;++j)
st[k][j][i]=Qry(k-1,st[k-1][j][i].l,st[k-1][j][i].r);
int l,r; while(q--){
rd(l),rd(r); int res=0; Data now = {l,r};
if(Chk(now)){ puts("0"); continue; }
if(!f1||!f2){ puts("-1"); continue; }
for(int i=17;i>=0;--i){
Data t = Qry(i,now.l,now.r); if(!Chk(t)) now=t,res|=1<<i;
} ++res,now=Qry(0,now.l,now.r),writeln(Chk(now)?res:-1);
}
}