#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ull = unsigned long long;

int nie[100001][50];

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

	vector<ll> fibs{1, 2};
	int f = 2;
	while(fibs.back() < 4e9) {
		fibs.push_back(fibs[f-1] + fibs[f-2]);
		++f;
	}

	int n, q;
	cin >> n >> q;

	vector<int> as(n);
	for(int i = 0; i < n; ++i) cin >> as[i];


	for(int k = 0; k < f; ++k) {
		nie[n][k] = n;
		map<ll, int> loc; 
		for(int i = n-1; i >= 0; --i) {
			nie[i][k] = nie[i+1][k];
			if(loc.contains(fibs[k] - as[i])) {
				nie[i][k] = min(nie[i][k], loc[fibs[k] - as[i]]);
			}
			loc[as[i]] = i;
		}
	}

	for(int i = 0; i < q; ++i) {
		int b, e;
		cin >> b >> e;
		++e;
		int s = 0;
		for(int k = 0; k < f; ++k) {
			if(nie[b][k] < e) ++s;
		}
		cout << s << '\n';
	}
	
	return 0;
}