### 问题描述 “那个帕鲁我已经观察你很久了，我对你是有些失望的，进了这个营地，不是把事情做好就可以的，你需要有体系化思考的能力。” 《幻兽帕鲁》火遍全网，成为了一款现象级游戏。 猫猫作为顶级帕鲁自然是首当其冲搭好了游戏私服，叫上好兄弟开始了愉快私服开荒。 但是这个游戏好玩归好玩，服务器有一堆 bug。比如说众所周知的内存泄漏问题。猫猫很无奈，写了一个脚本去检测服务器的内存占用问题，当超过一定数值就自杀。 但是问题又来了，服务器自杀了之后还要猫猫亲自去手动重启，配置守护进程的诸多方法都不适合。 最终，猫猫决定一分钟监听一次服务器端口是否正常放通。并记录下日志。 具体如下：**脚本每隔一分钟监听一次服务端口是否正常，如果服务没有正常运行，则输出 1 并重启服务，否则输出 0。** 现在日志形如一段 $01$ 字符串，$0$ 代表正常运行，$1$ 代表端口关闭。在定时任务监听中遇到端口关闭时会自动重启一次服务器。 现在拿到日志之后，猫猫想知道 $[l,r)$ 区间内到底有多少次重启成功。（$l$ 为起点时刻，$r$ 为终点时刻。） >注：重启成功为服务从端口关闭状态转换为端口正常运行状态。如果日志的最后一分钟为 $1$，那么你可以视作最后一分钟为重启失败。 ### 输入格式 第一行输入一个正整数 $n$。$(1\le n\le 2\times 10^5)$ 第二行输入一个长度为 $n$ 的 $01$ 字符串 $S$。$(|S|=n,s_i \in {\lbrace 0,1 \rbrace},1\le i\le n)$。 第三行输入一个正整数 $m$。$(1\le m\le 2\times 10^5)$ 接下来 $m$ 行，每行输入两个正整数 $l,r$，表示区间 $[l,r)$。$(1\le l< r\le n+1)$。 ### 输出数据 输出 $m$ 行，表示对于 $m$ 次查询的结果。 ### 样例输入 ``` 5 10110 4 1 2 1 3 2 4 2 5 ``` ### 样例输出 ``` 1 1 0 1 ``` ### 说明 对于第 $1$ 分钟，在重启后第 $2$ 分钟变成 $0$，说明第 $1$ 分钟重启成功。 对于第 $3$ 分钟，在重启后第 $4$ 分钟依旧是 $1$，说明第 $3$ 分钟重启失败。 对于第 $4$ 分钟，在重启后第 $5$ 分钟变成 $0$，说明第 $4$ 分钟重启成功。