#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for(int i=a; i<b; i++)
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
#define fo(i, n) rep(i, 0, n)
#define F first
#define S second
#define MP make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;

const int FMAX = 300;
const int NMAX = 112345;
const ll NUMMAX = 2123456789;

ll fib[FMAX];

int flen=2;

ll in[NMAX];
int mine[FMAX][NMAX];
int n,q;

int main() {
	fib[0]=1;
	fib[1]=2;
	while(fib[flen-1]<NUMMAX) {
		fib[flen] = fib[flen-1]+fib[flen-2];
		flen++;
	}

	scanf("%d%d", &n, &q); 
	fo(i,n) scanf("%lld", in+i);


	fo(i,flen)
	{
		fo(x,n) mine[i][x]=NMAX;
		int b=0, e=-1;
		int fcount = 0;
		map<ll, int> counts;
		while(e<n)
		{
			if(fcount)
			{
				counts[in[b]]--;
				fcount -= counts[fib[i]-in[b]];
				b++;

			}
			else
			{
				e++;
				fcount += counts[fib[i]-in[e]];
				counts[in[e]]++;
			}
			if(fcount) mine[i][b]=min(mine[i][b], e);
		}


	}

	fo(i,q)
	{
		int out=0;
		int b,e;
		scanf("%d%d", &b, &e);
		fo(i,flen) out += (mine[i][b]<=e);
		printf("%d\n", out);
	}

}