Dãy Fibonacci là dãy vô hạn các số tự nhiên bắt đầu bằng hai phần tử 0 và 1, các phần tử tiếp theo được thiết lập theo quy tắc, mỗi phần tử sau bằng tổng hai phần tử trước nó.

Các phần tử đầu tiên của dãy Fibonacci là : 0,1,1,2,3,5,8,…

Với một dãy số nguyên không âm a₁, a₂, …, a­_n và hai số nguyên P, Q, hãy đếm số số cặp chỉ số l, r thỏa mãn P ≤ r – l + 1 ≤ Q và đoạn con S (l,r) là dãy có tính Fibonacci.

Dữ liệu: vào từ thiết bị nhập chuẩn theo khuôn dạng:

• Dòng đầu gồm ba số nguyên dương n, P, Q ( 1 ≤ P ≤ Q ≤ n);
• Dòng thứ hai gồm n số nguyên không âm a₁, a₂, …, a­_n (a_i ≤ 10⁶).

Kết quả: ghi ra thiết bị ra chuẩn một dòng chứa một số nguyên là số lượng cặp chỉ số l, r đếm được.

Ràng buộc:

• Có 30% số lượng test ứng với 30% số điểm có n = 1;
• Có 20% số lượng test khác ứng với 20% số điểm có n ≤ 100;
• Có 30% số lượng test khác ứng với 30% số điểm có n ≤ 10⁴;
• Có 20% số lượng test còn lại ứng với 20% số điểm có n ≤ 10⁵;

Ví dụ: