Sereja và D
Cho dãy $a_1,a_2,...,a_N$ thỏa mãn: $a_1\le a_2\le ... \le a_N$.
Có $Q$ truy vấn, mỗi truy vấn chứa hai số nguyên $t$ và $d$. Hãy tìm chỉ số $i \ (1\le i\le N)$ nhỏ nhất thỏa mãn tồn tại chỉ số $k \ (i\le k\le N)$ sao cho: $a_i+d\ge a_{i+1}; a_{i+1}+d \ge a_{i+2}; ...; a_{k-1}+d\ge a_k; a_k \le t; a_{k+1} > t$.
Dữ liệu
- Dòng đầu tiên chứa hai số nguyên $N$ và $Q \ (0<N,Q\le 10^5)$;
- Dòng thứ hai chứa $N$ số nguyên $a_i \ (0<a_i\le 10^6)$;
- $Q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $t,d \ (0< t,d \le 10^6)$.
Kết quả
- In trên $Q$ dòng, mỗi dòng chứa một số nguyên là kết quả cho câu hỏi tương ứng.
Ví dụ
Ví dụ 1
input
5 6
1 2 3 10 50
1 1
5 3
11 7
100000 1
1000000 1000000
11 9
output
0
1
1
0
0
1
Comments