from collections import defaultdict
from copy import deepcopy

n, q = map(int, input().split())
a = list(map(int, input().split()))

segs = []
for _ in range(q):
    x, y = map(int, input().split())
    segs.append((x, y))

fibs = [1, 2]
while fibs[-1] + fibs[-2] <= 2000000005:
    fibs.append(fibs[-1] + fibs[-2])

last_occur = {}
lst = [-1 for _ in fibs]

lsts = []

for j, x in enumerate(a):
    for i, f in enumerate(fibs):
        if f-x in last_occur:
            lst[i] = max(lst[i], last_occur[f-x])
    lsts.append(lst.copy())
    last_occur[x] = j

for (a, b) in segs:
    ans = 0
    for l in lsts[b]:
        if l >= a:
            ans += 1
    print(ans)