Problem Statement

You are given a length-$N$ sequence $A = (A_1, \ldots, A_N)$ of non-negative integers. Answer $Q$ queries.

In the $i$-th query, you are given integers $L_i$ and $R_i$ such that $1 \leq L_i \leq R_i \leq N$. Solve the following problem for the subsequence $B = (A_{L_i}, \ldots, A_{R_i})$ of length $R_i - L_i + 1$.

We repeat the following operation on $B$:

• Choose integers $i$ and $j$ with $1 \leq i, j \leq |B|$ such that $B_i \ge 1$, $B_j \ge 1$, and $1 \leq j - i \leq 2$. Subtract $1$ from $B_i$ and $B_j$.

Find the maximum number of times the operation can be performed.

Constraints

• $1 \leq N \leq 200000$
• $1 \leq Q \leq 200000$
• $0 \leq A_i \leq 10^9$
• $1 \leq L_i \leq R_i \leq N$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

N Q
A_1 \cdots A_N
L_1 R_1
\vdots
L_Q R_Q

Output

Print $Q$ lines.

The $i$-th line should contain the maximum number of times the operation can be performed for $B = (A_{L_i}, \ldots, A_{R_i})$.