참새와 쿼리

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

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

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

• l r : 부분 수열 $[A_l, A_{l+1}, ..., A_r]$이 이면 , 아니면 를 출력한다.

첫째 줄에 수열의 길이 $N$과 쿼리의 개수 $Q$가 주어진다.

둘째 줄에 $N$개의 양의 정수 $A_1, A_2, \cdots, A_N$이 주어진다.

쿼리에 대한 답을 한 줄에 하나씩 출력한다.

• $2 \leq N \leq 200\ 000$.
• $1 \leq Q \leq 200\ 000$.
• $1\le A_i<$ .