Score : 1000 points
You are given a sequence a = \{a_1, ..., a_N\} with all zeros, and a sequence b = \{b_1, ..., b_N\} consisting of 0 and 1. The length of both is N.
You can perform Q kinds of operations. The i-th operation is as follows:
Minimize the hamming distance between a and b, that is, the number of i such that a_i \neq b_i, by performing some of the Q operations.
Input is given from Standard Input in the following format:
N b_1 b_2 ... b_N Q l_1 r_1 l_2 r_2 : l_Q r_Q
Print the minimum possible hamming distance.
3 1 0 1 1 1 3
1
If you choose to perform the operation, a will become \{1, 1, 1\}, for a hamming distance of 1.
3 1 0 1 2 1 1 3 3
0
If both operations are performed, a will become \{1, 0, 1\}, for a hamming distance of 0.
3 1 0 1 2 1 1 2 3
1
5 0 1 0 1 0 1 1 5
2
It may be optimal to perform no operation.
9 0 1 0 1 1 1 0 1 0 3 1 4 5 8 6 7
3
15 1 1 0 0 0 0 0 0 1 0 1 1 1 0 0 9 4 10 13 14 1 7 4 14 9 11 2 6 7 8 3 12 7 13
5
10 0 0 0 1 0 0 1 1 1 0 7 1 4 2 5 1 3 6 7 9 9 1 5 7 9
1