#include <bits/stdc++.h>
using namespace std;
#define int long long

int n, q;
int a[101010];
pair<int, int> qur[101010];
int resQ[101010];

vector<pair<int, int> > sgs;
void goLeft(int fib) {
    unordered_map<int, int> lastOccurNum;
    for (int i = 1; i <= n; i++) {
        if (fib - a[i] > 0 && lastOccurNum.find(fib - a[i]) != lastOccurNum.end()) {
            sgs.push_back({lastOccurNum[fib - a[i]], i});
        }
        lastOccurNum[a[i]] = i;
    }
}
void goRight(int fib) {
    unordered_map<int, int> lastOccurNum;
    for (int i = n; i >= 1; i--) {
        if (fib - a[i] > 0 && lastOccurNum.find(fib - a[i]) != lastOccurNum.end()) {
            sgs.push_back({i, lastOccurNum[fib - a[i]]});
        }
        lastOccurNum[a[i]] = i;
    }
}

int t[401010];
void build(int v, int vl, int vr) {
    t[v] = 0;
    if (vl == vr) return;
    int vm = (vl + vr) / 2;
    build(2 * v, vl, vm);
    build(2 * v + 1, vm + 1, vr);
}
void upd(int v, int vl, int vr, int pos, int val) {
    if (vl == vr) {
        t[v] = val;
        return;
    }
    int vm = (vl + vr) / 2;
    if (pos <= vm) upd(2 * v, vl, vm, pos, val);
    else upd(2 * v + 1, vm + 1, vr, pos, val);
    t[v] = max(t[2 * v], t[2 * v + 1]);
}
int gt(int v, int vl, int vr, int l, int r) {
    if (l <= vl && vr <= r) return t[v];
    if (r < vl || vr < l) return 0;
    int vm = (vl + vr) / 2;
    return max(gt(2 * v, vl, vm, l, r), gt(2 * v + 1, vm + 1, vr, l,  r));
}

vector<pair<int, int> > Events[101010];
void solve(int fib) {
    sgs.clear();
    goLeft(fib);
    goRight(fib);

    // cout << fib << " <<<<<<< " << endl;
    for (int i = 1; i <= n; i++) Events[i].clear();
    for (auto [l, r] : sgs) {
        // cout << l << " " << r << endl;
        Events[r].push_back({l, 0});
    }
    for (int i = 1; i <= q; i++) {
        Events[qur[i].second].push_back({i, 3});
    }

    build(1, 1, n);
    for (int i = 1; i <= n; i++) {
        for (auto [pos, tp] : Events[i]) {
            if (tp == 0) {
                upd(1, 1, n, pos, 1);
                continue;
            }
            int id = pos;
            int start = qur[id].first, finish = qur[id].second;
            int hv = gt(1, 1, n, start, finish);
            // if (hv) {
            //     cout << id << " HAVE   " << pos << " " << i << endl;
            // }
            resQ[id] += hv;
        }
    }
}

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

    // int a[60];
    // a[1] = 1;
    // a[2] = 2;
    // for (int i = 3; i <= 48; i++) {
    //     a[i] = a[i - 1] + a[i - 2];
    //     cout << a[i] << ",";
    // }
    // return 0;

    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    
    for (int i = 1; i <= q; i++) {
        cin >> qur[i].first >> qur[i].second;
        qur[i].first++;
        qur[i].second++;
    }
    
    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, 2971215073};
    for (int fib : Fibonaccis) {
        solve(fib);
    }
    
    for (int i = 1; i <= q; i++)
        cout << resQ[i] << '\n';
    return 0;
}