#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef pair<int, int> pii;
typedef vector<int> vi;

int n, q;
int a[101010];
unordered_map<int, int> cntOccurNum;
int FibSz = 45;
vector<int> Fibonaccis = {1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903};
int cntHv[50];
int curRes = 0;
void add(int ind, int end) {
    for (int id = 0; id < FibSz; id++) {
        int num = Fibonaccis[id];
        if (num <= a[ind]) continue;
        if (cntOccurNum.find(num - a[ind]) != cntOccurNum.end()) {
            cntHv[id]++;
            curRes += (cntHv[id] == 1);
        }
    }
    cntOccurNum[a[ind]]++;

    // cout << "ADD " << ind << "  " << curRes << endl;
}
void del(int ind, int end) {
    cntOccurNum[a[ind]]--;
    if (cntOccurNum[a[ind]] == 0) {
        cntOccurNum.erase(a[ind]);
    }

    for (int id = 0; id < FibSz; id++) {
        int num = Fibonaccis[id];
        if (num <= a[ind]) continue;
        if (cntOccurNum.find(num - a[ind]) != cntOccurNum.end()) {
            cntHv[id]--;
            curRes -= (cntHv[id] == 0);
        }
    }

    // cout << "DELETE " << ind << "  " << curRes << endl;
}


vi mo(vector<pii> Q) {
    int L = 0, R = 0, blk = 350;
    vi s(sz(Q)), res = s;
   #define K(x) pii(x.first/blk, x.second ^ -(x.first/blk & 1))
    iota(all(s), 0);
    sort(all(s), [&](int s, int t) {return K(Q[s]) < K(Q[t]); });
    
    L = Q[s[0]].first;
    R = Q[s[0]].first - 1;
    for (int qi : s) {
        pii q = Q[qi];
        while (L > q.first) add(--L, 0);
        while (R < q.second) add(++R, 1);
        while (L < q.first) del(L++, 0);
        while (R > q.second) del(--R, 1);
        res[qi] = curRes;
    }
    return res;
}

int32_t main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> q;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    vector<pii> Q(q);
    for (int i = 0; i < q; i++) {
        cin >> Q[i].first >> Q[i].second;
    }
    vector<int> ans = mo(Q);
    for (int i = 0; i < q; i++)
        cout << ans[i] << '\n';

    return 0;
}