[초등부] 2022 KOI 2차대회 대비 모의고사 (6월 4주차)

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

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

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

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

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

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

입력

첫 줄에 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)

출력

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

부분문제

번호	점수	조건
#1	30점	N <= 1000
#2	70점	추가적인 제한 조건이 없다.

장화
서브태스크

2초 512MB