1 tuần sau ...
Vì thời gian xa cách quá dài, được ở cạnh LN lâu thế này là một món quà vô giá với Ami. Ami vẫn không tin được. Thời gian có dài bao nhiêu, khi đứng cuối con đường nhìn lại, cũng như một cái chớp mắt. Tuy thời gian chỉ như một khoảnh khắc nhưng lại chứa biết bao âm hưởng thăng trầm, càng hạnh phúc hơn khi Ami có LN để cùng thưởng thức lại những kí ức ấy.
Ami và LN đều thích mặc áo dài, và hai bạn đang ở trong một tiệm may. May một chiếc áo dài, giá cả đương nhiên là không hề rẻ, nhưng với Ami, mọi khó khăn trên thế gian đều là vô nghĩa nếu cậu nhớ đến LN. Giờ đây, công việc của Ami chỉ là chọn loại áo dài đẹp nhất, đắt nhất, và vừa ý LN nhất. Vì Ami thương yêu LN mà, được chiều chuộng người yêu, âu cũng là một đặc quyền. Cửa hàng đang bán n loại áo dài, mỗi chiếc áo dài có mã số lần lượt từ 1, chiếc áo dài thứ i có giá là ai. Tiêu chuẩn của LN lại rất cao - LN chỉ thích những chiếc áo dài mang mã số từ L đến R. Và Ami lại không muốn mua những chiếc áo dài quá rẻ, do đó cậu sẽ loại ra những chiếc áo dài có giá tiền không vượt quá k. Các bạn hãy tính xem Ami đã loại ra bao nhiêu chiếc nhé.
Dữ liệu vào
Dòng đầu tiên là 1 số nguyên dương n - số chiếc áo dài (n <= 105).
Dòng tiếp theo gồm n số nguyên dương a1, a2, … , an( ai<=106).
Dòng thứ 3 là một số nguyên q - số đoạn L và R mà LN thích (q <= 105).
*Lưu ý rằng, giả sử x là kết quả của câu hỏi kề trước, ban đầu x = 1
khi đó L và R sẽ được tính như sau:
L = (L * x + x) % n + 1.
R = (R * x + x) % n + 1.
Nếu L > R, đổi 2 giá trị cho nhau.
Q dòng cuối cùng, mỗi dòng có dạng L, R , K (1 <= L <= R <= n , K <= 106).
Dữ liệu ra
Q dòng, mỗi dòng là một câu trả lời tương ứng.
Input
5
1 2 3 4 5
1
1 2 4
Output
2
Giải thích
Giá trị thực sự của câu hỏi là 3 4 4, xét đoạn con 3 4, cả 2 số đều không vượt quá 4, do đó kết quả là 2.