题目描述

我们给定一个整数 $n$ 代表我们的数组长度，接下来输入 $n$ 个数字代表我们的数组元素，我们数组只有 $0$ 和 $1$。

接下来 $k$ 次操作，每次操作给定两个整数 $l,\ r$ 询问这段区间内有多少个 $1$，数组下标从 $1$ 开始。输出 $k$ 行结果。

输入格式

第一行一个整数 $n$，表示数组长度。

第二行 $n$ 个整数，表示数组元素。

第三行一个整数 $k$，表示操作次数。

接下来 $k$ 行，每行两个整数 $l,\ r$，表示询问区间。

输出格式

对于每次询问，输出结果。

5
0 1 1 1 0
1
1 5

3

数据范围

$1 \le n \le 10^{6}$。

$1 \le k \le 10^{6}$。

$1 \le l \le r \le n$。