flip01

Time limit: 0.15s Memory limit: 32MB Input: flip.in Output: flip.out

Task

A flip operation on an array a1,a2,,aNa_1, a_2, \dots, a_N, consisting only of the digits 00 and 11, is performed in the following two steps:

  • Step 1: Choose two natural numbers ll and rr such that 1lrN1 \leq l \leq r \leq N.
  • Step 2: For each position ii in the interval [l,r][l, r], if aia_i is 00, it changes its value to 11, otherwise, it changes its value to 00 (from 00 to 11 and from 11 to 00).

Given NN, the array a1,a2,,aNa_1, a_2, \dots, a_N, and QQ queries of the form [st,dr][st, dr]:

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

Solve this problem and we will reward you with 100100 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 NN, representing the length of the array, followed by the array a1a_1, a2a_2, ..., aNa_N on the second line. The third line of the file will contain the number QQ, representing the number of queries. The next QQ lines will contain two numbers stst and drdr, 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 QQ queries on separate lines, in the order they were given.

Constraints and clarifications

  • 1N,Q2×1051 \leq N, Q \leq 2 \times 10^5
  • ai={0,1}a_i = \{ 0, 1 \}
  • For each query, 1stdrN1 \leq st \leq dr \leq N
# Points Constraints
1 9 a1=a2=a3=...=an1=ana_{1}=a_{2}=a_{3}=...=a_{n-1}=a_{n}
2 7 For every position ii, 1i<N1 \le i < N, aiai+1a_i \neq a_{i+1}
3 23 1N,Q2001 \leq N, Q \leq 200
4 21 200<N,Q2000200<N, Q \leq 2 000
5 40 2000<N,Q2×1052000<N, Q \leq 2 \times 10^5

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][2, 2] and [4,4][4, 4].

Example 2

flip.in

1
1
1 
1 1

flip.out

1

Log in or sign up to be able to send submissions!