Truy vấn trên mảng

Cho một mảng $a$ gồm $n$ số nguyên dương, mỗi phần tử không vượt quá $n$.

Bạn cần xử lý $q$ truy vấn trên mảng này. Mỗi truy vấn gồm hai số $p$ và $k$. Trong mỗi truy vấn, ta thực hiện lặp lại thao tác sau: thay $p$ bằng $p+a_p+k$. Thao tác được lặp cho đến khi $p$ trở nên lớn hơn $n$. Đáp án của truy vấn là số thao tác đã thực hiện.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên $n$.
• Dòng thứ hai chứa $n$ số nguyên — các phần tử của mảng $a$.
• Dòng thứ ba chứa số nguyên $q$.
• $q$ dòng tiếp theo, mỗi dòng chứa hai số $p$ và $k$ tương ứng với một truy vấn.

Dữ liệu ra

In ra $q$ số nguyên, mỗi số trên một dòng: số thứ $i$ là đáp án của truy vấn thứ $i$.

Ràng buộc

• $1\le n\le {10}^5$
• $1\le a_i\le n$ với mọi $i$ từ $1$ đến $n$
• $1\le q\le {10}^5$
• $1\le p,k\le n$

Ví dụ