Given a binary sequence $a$ of length $n$ and $q$ queries. For each query $[l, r]$, we want to calculate the sum of lengths of all subarrays $a[i \dots j]$ ($l \le i \le j \le r$) such that the number of $0$s equals the number of $1$s in that subarray.
**Task**: Given $n, q$ and the array $a$, answer $q$ queries.
#### Input
- The first line contains two integers $n$ and $q$ ($1 \le n, q \le 2 \times 10^5$).
- The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($a_i \in \{0, 1\}$).
- Each of the next $q$ lines contains two integers $l$ and $r$ ($1 \le l \le r \le n$).
#### Output
- Print $q$ lines, each containing the answer for the corresponding query.
#### Example
Input:
```
5 2
1 0 1 0 1
1 5
2 4
```
Output:
```
16
4
```
#### Subtasks
- **Subtask 1 (20 points)**: $n \le 1000, q \le 10^5$.
- **Subtask 2 (20 points)**: $n \le 10^5, q \le 1000$.
- **Subtask 3 (60 points)**: No additional constraints.
