Hyunuk 有一个由 $n$（$2 \le n \le 2 \cdot 10^5$）个格子组成的长筒。每个格子要么是空的，要么包含一颗珠子。在储存珠子时，如果它们散落遍地会显得很不美观，因此 Hyunuk 想要将所有珠子聚集在其中一端。具体来说，如果长筒内有 $k$ 颗珠子，那么这些珠子必须位于第 $1$ 到第 $k$ 个格子中，或者位于第 $n - k + 1$ 到第 $n$ 个格子中。

Hyunuk 可以通过轻轻推动，将长筒中第 $i$ 个格子内的珠子移动到第 $i-1$ 个格子或第 $i+1$ 个格子。如果被移动到的目标格子中已有珠子，该珠子也会被推向相同的方向。例如，假设第 2、3 和 5 个格子中各有珠子。如果 Hyunuk 将第 2 个格子中的珠子推向第 3 个格子，那么第 3 个格子中的珠子也会被推到第 4 个格子。第 5 个格子中的珠子则保持原位。

Hyunuk 想知道，当他在长筒中添加或移除珠子时，整理所有珠子所需的最少移动次数会如何变化。请编写一个程序，计算在 Hyunuk 插入或移除长筒中的珠子时，整理长筒中所有珠子所需的最少移动次数。

输入格式

第一行包含一个整数 $n$（$2 \le n \le 2 \cdot 10^5$），表示长筒的长度。

第二行包含一个长度为 $n$ 的字符串，仅由字符 O 和 X 组成，表示长筒的初始状态。如果字符串的第 $i$ 个字符是 O，则表示该格子中有一颗珠子；否则，第 $i$ 个字符是 X，表示该格子为空。

第三行包含一个整数 $q$（$1 \le q \le 2 \cdot 10^5$），表示 Hyunuk 进行的操作次数。

接下来的 $q$ 行，每行包含一个整数 $k$（$1 \le k \le n$），表示 Hyunuk 的操作。这意味着，如果长筒的第 $k$ 个格子中已有珠子，则将其移除；如果该格子中没有珠子，则在此位置插入一颗珠子。

输入数据保证长筒中永远不会出现零颗珠子的状态。

输出格式

输出 $q$ 行，其中第 $i$ 行包含一个整数，表示在 Hyunuk 完成前 $i$ 次操作后，整理所有珠子所需的最少移动次数。

样例

输入样例 1

6
OXXOXO
4
3
1
6
3

输出样例 1

2
1
2
2