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 = {}

lsts = []

for j, x in enumerate(a):
    for i, f in enumerate(fibs):
        if f-x in last_occur:
            if f not in lst:
                lst[f] = [(last_occur[f-x], j)]
            elif last_occur[f - x] > lst[f][-1][0]:
                lst[f].append((last_occur[f-x], j))
    lsts.append(deepcopy(lst))
    last_occur[x] = j

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