RoAlgo PreOJI 2024 VI | flip01

Task

A flip operation on an array $a_1, a_2, \dots, a_N$, consisting only of the digits $0$ and $1$, is performed in the following two steps:

• Step 1: Choose two natural numbers $l$ and $r$ such that $1 \leq l \leq r \leq N$.
• Step 2: For each position $i$ in the interval $[l, r]$, if $a_i$ is $0$, it changes its value to $1$, otherwise, it changes its value to $0$ (from $0$ to $1$ and from $1$ to $0$).

Given $N$, the array $a_1, a_2, \dots, a_N$, and $Q$ queries of the form $[st, dr]$:

For each given query, find the minimum number of flip operations needed, starting from the initial array, such that for every position $i$ in the interval $[st, dr]$, $a_i$ is equal to $0$.

Solve this problem and we will reward you with $100$ points! (or, as much as you can...).

The operations performed for each query DO NOT carry over to subsequent queries (in other words, all queries start from the initial array).

Input data

The first line of the input file flip.in will contain the number $N$, representing the length of the array, followed by the array $a_1$, $a_2$, ..., $a_N$ on the second line. The third line of the file will contain the number $Q$, representing the number of queries. The next $Q$ lines will contain two numbers $st$ and $dr$, which represent the endpoints of the interval for which we want to find the answer to the question in the statement.

Output data

The output file flip.out will contain the answers to the $Q$ queries on separate lines, in the order they were given.

Constraints and clarifications

• $1 \leq N, Q \leq 2 \times 10^5$
• $a_i = \{ 0, 1 \}$
• For each query, $1 \leq st \leq dr \leq N$

Example 1

flip.in

5
0 1 0 1 1
3
4 5
4 4
1 4

flip.out

1
1
2

Explanation

For the third query, we need to use the flip operation for the intervals $[2, 2]$ and $[4, 4]$.

Example 2

flip.in

1
1
1 
1 1

flip.out

1