AT_jag2018summer_day2_j AB Sort

你有一个长度为 $N$、有且仅有 $A$ 和 $B$ 的字符串。你需要处理$Q$次询问。 对于第$i$次询问，你会得到 $l_i$ 和 $r_i$ 两个数。之后，对于每一个 $x$ （$l_i\le x \le r_i$）, $s_x$ 更改为另一个字母，就是 $A$ 改为 $B$ ， $B$ 改为 $A$ 。 每次查询后，你需要计算函数 $f$（$B+s+A$）,即在字符串$s$前添加一个$B$,后添加一个$A$。给定字符串 $t$ 。函数 $f$（$t$） 的返回值是一个非负整数。$f$（$t$）函数应遵循一下更改规则： - 对于字符串$t$中所有形如$BA$的字串,请用形如$AB$的字串代替。 - $f$（$t$）函数的返回值是将字符串 $t$ 变成没有形如$BA$的字串所需要的替换次数。 例如$f$（$ABAB$）的返回值为$1$，$f$（$BBAA$）的返回值为$3$，$f$（$AAA$）的返回值为$0$。

输入一共$Q+3$行。 第一行共一个正整数$N$。 第二行有一个长度为$N$的字符串$s$。 第三行有一个正整数$Q$。 之后$Q$行每一行两个正整数$l_i$与$r_i$。

输出一共$Q$行。 每一行有一个正整数$f$（$A+B+s$）。

- $1$ $\le$ $N$ $\le$ $200000$ - |$s$| = $N$ - 字符串$s$只包含$A$和$B$两种字符。 - $1$ $\le$ $Q$ $\le$ $200000$ - $0$ $\le$ $l_i$ $\le$ $r_i$ $\le$ $N-1$ - $N，Q，l_i，r_i$ 都是整数。 ### 样例解释 在第一次查询后，字符串$s$被更改为了$BBBAA$，所以需要排序的字符串为$BBBBAAA$，即输出$f$（$BBBBAAA$）的值。第二次查询后，字符串$s$被更改为了$AAAAA$,所以需要排序的字符串为$BAAAAAA$，即输出$f$（$BAAAAAA$）的值。