Đề bài

Cho một dãy số nguyên dương gồm \(N\) phần tử \(a_1, a_2, \ldots, a_N\) và \(Q\) truy vấn.

Mỗi truy vấn gồm 2 số nguyên dương \(p\) và \(k\). Trong một lượt hành động bạn phải thực hiện phép gán:

Yêu cầu: Với mỗi truy vấn, hãy tính số lần thực hiện hành động tối thiểu để \(p > N\).

Dữ liệu vào

• Dòng đầu tiên gồm một số nguyên dương \(N\) (\(1 \leq N \leq 10^5\)) — số phần tử của dãy.
• Dòng thứ hai gồm \(N\) số nguyên dương \(a_1, a_2, \ldots, a_N\) (\(1 \leq a_i \leq N\)).
• Dòng thứ ba gồm số nguyên dương \(Q\) (\(1 \leq Q \leq 10^5\)) — số lượng truy vấn.
• \(Q\) dòng tiếp theo, mỗi dòng gồm hai số nguyên dương \(p\) và \(k\) (\(1 \leq p, k \leq N\)).

Dữ liệu ra

• Đối với mỗi truy vấn, in ra số lần thực hiện hành động tối thiểu để \(p > N\).

Giới hạn

• Subtask 1 [20% số test]: \(N, Q \leq 10^3\)
• Subtask 2 [30% số test]: \(a_1 = a_2 = \ldots = a_N\)
• Subtask 3 [50% số test]: \(N, Q \leq 10^5\)

Sample Input 1

3
1 1 1
3
1 1
2 1
3 1

Sample Output 1

2
1
1

Giải thích

• Truy vấn 1: Bắt đầu tại \(p = 1\), thực hiện \(p = p + a_p + k = 1 + 1 + 1 = 3\), sau đó \(p = 3 + 1 + 1 = 5 > 3\), cần 2 bước.
• Truy vấn 2: \(p = 2 + 1 + 1 = 4 > 3\), cần 1 bước.
• Truy vấn 3: \(p = 3 + 1 + 1 = 5 > 3\), cần 1 bước.