题目背景

English statement: https://www.luogu.com.cn/problem/T595299

题目描述

小 O 非常爱去电 $\texttt{van}$ 城，所以他对 $\texttt{van}$ 这个字符串非常的感兴趣，于是他出了一道和 $\texttt{van}$ 有关的字符串题。

给你一个长度为 $n$ 的字符串 $s$，保证 $s$ 由 $\texttt{v}$、$\texttt{a}$、$\texttt{n}$ 三种字符构成，设 $s_i$ 表示 $s$ 的第 $i$ 个字符。

接下来小 O 会给你 $m$ 次操作，每次操作给出一个整数 $x(1\le x\le n-1)$，表示你需要交换 $s_x$ 和 $s_{x+1}$。

在每次操作结束后，你需要输出字符串中 $\texttt{van}$ 作为子序列的出现次数。

• 一个字符串 $t$ 是字符串 $s$ 的子序列，当且仅当可以从 $s$ 中删除若干个字符（可以为 $0$ 个），将剩下的字符按在 $s$ 中的顺序依次相接得到 $t$。

输入格式

输入共 $m+2$ 行。

第一行有两个整数 $n,m$，分别表示字符串长度和操作次数。

第二行有一个长度为 $n$ 的字符串 $s$。

第 $3\sim m+2$ 行，第 $i+2$ 行一个整数 $x_i$，表示第 $i$ 次操作给出的 $x$。

输出格式

输出共 $m$ 行，第 $i$ 行输出一个整数表示第 $i$ 次操作结束后的答案。

8 3
vvvaannn
4
3
5

18
15
12

提示

样例 #1 解释

初始时 $s=\texttt{vvvaannn}$。

第一次操作交换 $s_4$ 和 $s_5$，此时 $s=\texttt{vvvaannn}$，$\texttt{van}$ 作为子序列出现了 $18$ 次。

第二次操作交换 $s_3$ 和 $s_4$，此时 $s=\texttt{vvavannn}$，$\texttt{van}$ 作为子序列出现了 $15$ 次。

第三次操作交换 $s_5$ 和 $s_6$，此时 $s=\texttt{vvavnann}$，$\texttt{van}$ 作为子序列出现了 $12$ 次。

数据范围

对于 $100\%$ 的数据，$3\le n\le 10^6$，$1\le m\le 10^6$，$s_i\in\{\texttt{v,a,n}\}$。

具体测试点限制如下表：

测试点编号	$n$ 的范围	$m$ 的范围	特殊性质
$1,2$	$n\le 3$	$m\le 100$	无
$3\sim 5$	$n\le 100$
$6\sim 9$	$n\le 3000$	$m\le 3000$
$10\sim 12$	$n\le 10^6$	$m=1$
$13\sim16$	$n\le 10^5$	$m\le 10^5$	A
$17,18$			无
$19,20$	$n\le 10^6$	$m\le 10^6$

特殊性质 A：对于交换操作，保证 $s_x$ 和 $s_{x+1}$ 中至少有一个为 $\texttt{a}$。