#include <bits/stdc++.h>

#define int long long
#define double long double
#define F first
#define S second
using namespace std;

void solve(){
    int n,q;
    cin>>n>>q;
    int x=1,y=1,c=2;
    vector<int>fib;
    fib.push_back(1);
    fib.push_back(1);
    fib.push_back(2);
    while(c<=2e9){
        x=y,y=c;
        c=x+y;
        fib.push_back(c);
    }
    map<int,int>mp;
    int a[n];
    vector<int>lst[n+1];
    for(int i=0;i<n;i++){
        cin>>a[i];
            for(int j=0;j<fib.size();j++){
                if(mp.find(fib[j]-a[i])!=mp.end()){
                    lst[i].push_back(mp[fib[j]-a[i]]);
                }
                else{
                    lst[i].push_back(-1);    
                }
            }
        mp[a[i]]=i;
    }
     vector<pair<int,int>>zap[n];
    for(int i=0;i<q;i++){
        int x,y;
        cin>>x>>y;
        zap[y].push_back({x,i});
    }
    int res[q+1];
    int ls[50];
    memset(ls,-0x3f,sizeof ls);
    for(int i=0;i<n;i++){
        for(int j=0;j<fib.size();j++){
           
            if(lst[i][j]!=-1){
                ls[j]=max(ls[j],lst[i][j]);
            }
        }
        for(auto &[l,x]:zap[i]){
            int r=0;
            for(int j=0;j<fib.size();j++){
                r+=(ls[j]>=l);
            }
            res[x]=r;
        }
    }
    for(int i=0;i<q;i++){
        cout<<res[i]<<endl;
    }
}
/*
2
3 6 2 5 2
7 4 3 1 4

*/
int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t=1;
    // cin>>t;
    for(int i=1;i<=t;i++){
        solve();
    }
    return 0;
}