n, q = tuple(map(int, input().split(" ")))
holes = list(map(int, input().split(" ")))

intervals = []
for _ in range(q):
    a, b = tuple(map(int, input().split(" ")))
    intervals.append((a, b))

sums = {inter: set() for inter in intervals}

for a, b in intervals:
    for i in range(a, b + 1):
        for j in range(i + 1, b + 1):
            sums[(a, b)].add(holes[i] + holes[j])

f_0 = 1
f_1 = 2

interval_days = {inter: 0 for inter in intervals}
max_sum = max(map(max, sums.values()))

while f_0 <= max_sum:
    f_2 = f_0 + f_1
    f_0 = f_1
    f_1 = f_2

    for interval in intervals:
        if f_0 in sums[interval]:
            interval_days[interval] += 1

for inter in intervals:
    print(interval_days[inter])