J. intervals
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given an array $$$A$$$ with $$$n$$$ integers. If an interval $$$[L,R]$$$ satisfies that the sequence $$$(A_L,A_{L+1},\cdots,A_R)$$$ has at least an odd number and at least an even number, we consider the interval $$$[L,R]$$$ as a perfect interval.

Now you are given $$$q$$$ questions, each question contains an interval $$$[X,Y]$$$. You need to answer how many intervals $$$[L,R]$$$ satisfying $$$(X \leq L \leq R \leq Y)$$$ are perfect.

Input

The first line contains two integers $$$n$$$ and $$$q$$$ $$$(1 \leq n,q \leq 5\cdot 10^5)$$$, indicating the length of array $$$A$$$ and the number of questions.

The second line contains $$$n$$$ integers, indicating $$$A_i$$$ $$$(0\leq A_i \leq 10^9)$$$.

From the third line to $$$(q+2)$$$-th line each line contains two intergers $$$X$$$ and $$$Y$$$ $$$(1 \leq X \leq Y \leq n)$$$, indicating the interval $$$[X,Y]$$$.

Output

The output has $$$q$$$ lines, each line contains one interger, indicating the answer of each question.

Example
Input
10 5
1 3 4 1 3 4 3 1 7 9
1 5
3 9
2 10
4 7
1 2
Output
8
17
29
5
0