A9038. Eugeny and Array

Eugeny has array $a=a_{1},a_{2},...,a_{n}$ , consisting of $n$ integers. Each integer $a_{i}$ equals to -1, or to 1. Also, he has $m$ queries:

- Query number $i$ is given as a pair of integers $l_{i}$ , $r_{i}$ $(1<=l_{i}<=r_{i}<=n)$ .
- The response to the query will be integer $1$ , if the elements of array $a$ can be rearranged so as the sum $a_{li}+a_{li}+1+...+a_{ri}=0$ , otherwise the response to the query will be integer $0$ .

Help Eugeny, answer all his queries.

The first line contains integers $n$ and $m$ $(1<=n,m<=2·10^{5})$ . The second line contains $n$ integers $a_{1},a_{2},...,a_{n}$ $(a_{i}=$ - $1,1)$ . Next $m$ lines contain Eugene's queries. The $i$ -th line contains integers $l_{i},r_{i}$ $(1<=l_{i}<=r_{i}<=n)$ .

Print $m$ integers — the responses to Eugene's queries in the order they occur in the input.