OJ现已增加邮箱找回密码功能，还没有绑定邮箱的同学们请抓紧时间，以免密码丢失无法找回
问题 I: 求和求和再求和！（hard version）
时间限制: 2 Sec 内存限制: 128 MB提交: 19 解决: 8
[提交] [状态] [讨论版] [命题人:]
题目描述
给定一个长度为n的01序列（该序列元素为0或者1）和该序列的一些长度为偶数的区间[l，r]。
对于每个区间，请你计算：
输入
第一行给出一个整数n（2<=n<=1000000），表示序列的长度。
第二行给出n个整数，表示给出的序列。
第三行给出一个整数q（1<=q<=1000000），表示区间的数量。
接下来q行，每行给出两个整数l，r（1<=l<r<=n）。
输出
输出q行，每行输出一个整数作为答案。
样例输入 Copy
8
0 1 0 1 0 1 0 1
2
2 7
1 8
样例输出 Copy
6
10