34123번 - 참새와 쿼리

$k$ 마리의 참새가 왼쪽 또는 오른쪽을 바라보며 일렬로 앉아 있다. 각 참새는 자기 자신과 마주 보고 있는 참새의 수만큼 운다. 즉, 어떤 참새가 왼쪽을 바라보고 있다면, 자신보다 왼쪽에 있으면서 오른쪽을 바라보는 참새의 수만큼 운다. 반대로 오른쪽을 바라보고 있다면, 자신보다 오른쪽에 있으면서 왼쪽을 바라보는 참새의 수만큼 운다.

수열 $(a_1, a_2, \dots, a_k)$가 참새 수열이라는 말은, $1 \leq i \leq k$인 모든 정수 $i$에 대하여 왼쪽에서부터 $i$번 참새가 정확히 $a_i$번 울도록 $k$마리의 참새들이 바라볼 방향을 고를 수 있다는 것이다.

$N$개의 양의 정수 $A_1, A_2, \dots, A_N$이 주어질 때, 다음 쿼리를 수행하는 프로그램을 작성하시오:

• $l$ $r$ : 수열 $(A_l, A_{l+1}, ..., A_r)$이 참새 수열이면 YES, 아니면 NO를 출력한다.

다음과 같은 형식으로 입력이 주어진다.

$N$ $Q$

$A_1$ $A_2$ $\cdots$ $A_N$

$l_1$ $r_1$

$\vdots$

$l_Q$ $r_Q$

각 줄마다 쿼리에 대한 답을 출력한다.

• $2 \leq N \leq 200\ 000$
• $1 \leq Q \leq 200\ 000$
• $1 \leq A_i < N$ ($1 \leq i \leq N$)
• $1 \leq l_i \leq r_i \leq N$ ($1 \leq i \leq Q$)