Welcome Back Contest: 2025 Problem 4

Alice, who is not in wonderland, would like to go, so she enters into a raffle for a chance to go for free! She gets a connected strip of ~N~ raffle tickets, each with an number written on it. The raffle is quite strange, allowing for multiple tickets to have the same number so that multiple people can win with the same number. She numbers the tickets from ~1~ to ~N~ from left to right, which she calls their index. While she is waiting for the raffle draw, she wonders the following:

Define a "connected group" of tickets to be all the tickets with indices from ~i~ to ~j \, (i \le j)~ inclusive. Two connected groups of tickets are said to be different if their starting or ending index differs.

If you are given indices ~l~ and ~r \, (l \le r)~, how many distinct connected groups of tickets exist in that range such that the sum of their numbers are even?

Alice needs your help to answer her ~Q~ questions!

Input Specification

The first line contains the integers ~N~, ~Q~, each separated by a space.

The next line contains the numbers ~a_1, a_2, ... a_N~ written on the raffle tickets, from left to right, each separated by a space.

The next ~Q~ lines contains indices ~l_i~ and ~r_i~ for the ~i~-th question.

Output Specification

For each question, output the answer on its own line.

Constraints

~1 \le N, Q \le 10^5~

~1 \le a_i \le 10^3~

~1 \le l_i \le r_i \le N~

Sample Input 1

5 3
2 1 3 2 3
2 4
1 5
3 5

Output for Sample Input 1

3
7
2

Explanation of Output for Sample Input 1

For the first question, you are given ~l=2~ and ~r=4~, which represents the tickets ~[1,3,2]~. The ~3~ connected groups that have even sums that exist within this range are ~[1,3]~, ~[2]~, and ~[1,3,2]~.

For the second question, you are given ~l=1~ and ~r=5~ which represents the tickets ~[2,1,3,2,3]~. The ~7~ connected groups that have even sums that exist within this range are ~[2]~,~[2,1,3]~, ~[2,1,3,2]~, ~[1,3]~, ~[1,3,2]~, ~[3,2,3]~, ~[2]~. Notice that ~[2]~ appears twice, as there are ~2~ different connected groups that look identical.

For the third question, you are given ~l=3~ and ~r=5~, which represents the tickets ~[3,2,3]~. The ~2~ connected groups that have even sums that exist within this range are ~[2]~, and ~[3,2,3]~.

Sample Input 2

9 5
2 1 3 5 2 4 4 2 3
1 9
3 6
2 2
5 8
4 7

Output for Sample Input 2

21
6
0
10
6