#include <bits/stdc++.h>

using namespace std;

#define For(i, a, n) for(int i =a;i<n;i++)
#define endl '\n'
#define vec vector

typedef long long ll;
typedef pair<ll, ll> pii;
template<typename... Args>
void dbg(Args&&... args){
    ((cerr<<args<<" |"),...);
    cerr<<endl;
}
template<class A, class B>
pair<A, B> operator+(const pair<A, B>&a, const pair<A, B>& b){
    return {a.first +b.first, a.second + b.second};
}
template<class A, class B>
ostream& operator<< (ostream& os, const pair<A, B>& a){
    return os<<"("<<a.first<<", "<<a.second<<")";
}
template<class A, class B, class C>
basic_ostream<A, B>& operator<<(basic_ostream<A, B>& os, const C&c){
    for(auto it=begin(c); it!=end(c);++it){
        os<<(it==begin(c)?"":" ")<<*it;
    }
    return os;
}
void solve(){

    vec<ll> fib = {1, 2};
    do{
        ll t = fib[fib.size()-1] + fib[fib.size()-2];
        fib.push_back(t);
    }while(fib.back() < 1000000000);
    dbg(fib.size(), fib);

    int fs = fib.size();
    int n, q;cin>>n>>q;
    vec<vec<int>> p (n + 1, vec<int>(fs));
    map<int, int> m;
    For(i, 1, n + 1){
        int a;cin>>a;
        For(j, 0, fs){
            p[i][j] = p[i-1][j];
            ll d= fib[j] -a;
            if(d <=0)continue;
            if(m.count(d)) p[i][j] = max(p[i][j], m[d]);
        }
        m[a] = i;
    }
    For(i, 0, q){
        int z, k;cin>>z>>k;
        z++, k++;
        ll ans = 0;
        For(j, 0, fs){
            if(p[k][j]>=z)ans++;
        }
        cout<<ans<<endl;
    }
}

main(){
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    int t=1;//cin>>t;
    while(t--){
        solve();
    }
}