1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define N 100005

 4 #define mid (l+r>>1)

 5 #define inf 1000000000

 6 int V,n,m,k,x,y,a[N],b[N],r[N],f[N*20],ls[N*20],rs[N*20];

 7 void update(int k1,int &k2,int l,int r,int x){

 8     k2=++V;

 9     ls[k2]=ls[k1];

10     rs[k2]=rs[k1];

11     f[k2]=f[k1]+1;

12     if (l==r)return;

13     if (x<=mid)update(ls[k1],ls[k2],l,mid,x);

14     else update(rs[k1],rs[k2],mid+1,r,x);

15 }

16 int query(int k1,int k2,int l,int r,int p){

17     if (l==r)return l;

18     if (f[rs[k2]]-f[rs[k1]]>=p)return query(rs[k1],rs[k2],mid+1,r,p);

19     return query(ls[k1],ls[k2],l,mid,p-f[rs[k2]]+f[rs[k1]]);

20 }

21 int main(){

22     while (scanf("%d%d",&n,&m)!=EOF){

23         V=0;

24         for(int i=1;i<=n;i++)scanf("%d",&a[i]);

25         for(int i=1;i<=n;i++)b[i]=a[i];

26         sort(b+1,b+n+1);

27         int k=unique(b+1,b+n+1)-b-1;

28         for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+k+1,a[i])-b;

29         for(int i=1;i<=n;i++)update(r[i-1],r[i]=++V,1,k,a[i]);

30         for(int i=1;i<=m;i++){

31             scanf("%d%d",&x,&y);

32             int ma=min(y-x+1,45),flag=0;

33             for(int j=1;j<=ma;j++){

34                 a[j]=query(r[x-1],r[y],1,k,j);

35                 if ((j>2)&&(b[a[j-1]]+b[a[j]]>b[a[j-2]])){

36                     printf("%lld\n",0LL+b[a[j]]+b[a[j-1]]+b[a[j-2]]);

37                     flag=1;

38                     break;

39                 }

40             }

41             if (!flag)printf("-1\n");

42         }

43     }

44 }