Sereja và D


Submit solution

Points: 1
Time limit: 1.0s
Memory limit: 1G

Problem type

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

There are no comments at the moment.