Page not loading? Try clicking here.
Placeholder

#5155
Subtask

장화 2s 512MB

Problems

시훈이는 길이 N의 눈길을 걸어가려고 한다.

눈길은 길이 1 단위로 N칸으로 나누어져 있으며 i번째 칸의 눈의 깊이는 a_i이다.

시훈이는 1번 칸에서 출발해 N번 칸으로 이동하려고 한다.

시훈이는 Q개의 부츠를 가지고 있다.

i번째 부츠를 신으면 깊이가 s_i 이하인 칸들을 밟을 수 있고 한 걸음에 최대 d_i 칸을 이동할 수 있다.

각 부츠마다 시훈이가 그 부츠를 신고 출발했을 때 N번째 칸으로 이동할 수 있을지 계산해주자.


Input

첫 줄에 N, Q가 주어진다. (1 \le N, Q \le 100000)

두 번째 줄에 a_i들이 차례로 주어진다. (0 \le a_i <= 10^9, a_1 = a_N = 0)

이후 Q줄에 걸쳐 각 줄마다 s_i, d_i가 주어진다. (0 \le s_i \le 10^9,​ 1 \le d_i \le N)


Output

입력에서 주어진 순서대로 총 Q줄에 걸쳐 i번째 줄에는 i번째 부츠를 신고 이동할 수 있다면 1을, 없다면 0을 출력하라.


Subtask

# Score Condition
#130

N <= 1000

#270

추가적인 제한 조건이 없다.


Example 

8 7

0 3 8 5 6 9 0 0

0 5

0 6

6 2

8 1

10 1

5 3

150 7
0

1

1

0

1

1

1


Source

USACO 2018 February Silver

You must sign in to write code.