Cho trước một mảng gồm \(n\) số nguyên \(a_1, a_2... a_n\) đã được sắp xếp tăng dần. Dựa trên mảng số này, bạn cần phải trả lời \(m\) truy vấn, mỗi câu hỏi gồm một cặp số kì diệu là \(t\) và \(d\).

Nhiệm vụ của bạn ở mỗi truy vấn là cần tìm ra vị trí \(l\) nhỏ nhất sao cho với vị trí \(l\) đó, thì tồn tại một vị trí \(r\) \((l \le r)\) thỏa mãn:

\(a_l + d \ge a_{l+1}, a_{l+1} + d \ge a_{l+2} ... , a_{r-1} + d \ge a_{r}, a_r \le t\) và \(a_{r+1} \gt t\) (nếu tồn tại \(a_{r+1}\))

Yêu cầu

• Hãy trả lời tất cả các truy vấn?

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên dương \(n\)
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2... a_n\) phân tách nhau bởi dấu cách.
• Dòng thứ ba chứa chứa số nguyên dương \(m\)
• Trên \(m\) dòng tiếp theo, mỗi dòng chứa một cặp số kì diệu \(t\) và \(d\) thể hiện một truy vấn.

Dữ liệu ra

• Với mỗi truy vấn, in ra kết quả trên một dòng.

Ràng buộc

• \(1 \le n,m \le 10^5\)
• \(1 \le a_i \le 10^6\)
• \(0 \le d \le 10^6\)
• \(a_1 \le t \le 10^6\)

Input 1

5
1 2 3 10 50
6
1 1
5 3
11 7
100000 1
1000000 1000000
11 6

Output 1

1
1
1
5
1
4