You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小 A 很喜欢玩祖玛，请你帮他写一个祖玛游戏的计算得分的程序。

祖玛游戏初始时会给出一串长度为 $n$ 的小球序列，每个小球都有着特定的颜色，颜色为 $[1,m]$ 内的正整数。

然后玩家会进行若干次操作，每次操作给出形如 $c,x$ 两个整数，接下来为了方便用二元组 $(c,x)$ 表示。其意义为在当前状态下的第 $c$ 个小球的后面打入一个颜色为 $x$ 的小球。如果 $c=0$，则代表在序列头部打入，若当前状态下小球个数小于 $c$，则代表在序列末尾追加。

每次操作后，请你计算该次操作带来的得分。如果一次操作后，序列中出现了不少于 $3$ 个连续的同色小球，则这一段极长的连续同色小球会被消去，并获得消去个数 $\times 2$ 的得分。消去之后，剩余的两段会拼接到一起，如果又出现了长度不小于 $3$ 的连续同色段，则继续消去并累计得分，规则同上，直到不出现长度不小于 $3$ 的连续同色段为止。

若玩家的所有操作结束后，仍有 $k$ 个小球剩余，则最后再计 $k$ 的得分。

举个例子：初始小球序列为 $211223$：

• 玩家进行 $(1,1)$ 操作
• 则在第 $1$ 颗珠子后面追加一颗 $1$：$2{\color{red}1}11223$；
• 此时出现了长度为 $3$ 的连续同色段（用绿色标出）$2{\color{green}111}223$，消去，然后计 $2\times3 = 6$ 分；
• 此时珠子串又变为 ${\color{green}222}3$，消去，计 $2\times 3 = 6$ 分。
• 此时珠子串只剩一颗 $3$。
• 若玩家不再进行操作，则再计 $1$ 分，总得分为 $6+6+1=13$。

输入输出格式

输入格式

第一行两个正整数 $n,m,p$，分别代表初始小球的个数、颜色的种数以及玩家的操作次数。

第二行 $n$ 个正整数 $a_i$，表示祖玛游戏的初始状态。

接下来的 $p$ 行每行两个整数 $c_i,x_i$，表示一次玩家的操作，意义如上。

输出格式

一行一个整数，表示总得分。

输入输出样例

6 3 1
2 1 1 2 2 3
1 1

13

数据规模

• 对于 $30\%$ 的数据，保证 $1\le n,m,p\le 10$；
• 对于另外 $10\%$ 的数据，保证 $x_i = 0$；
• 对于另外 $10\%$ 的数据，保证 $x_i = n + p$；
• 对于 $100\%$ 的数据，$1\le n,m,p\le 2000$，$1\le a_i\le m$，$0\le c_i\le n + p$，$1\le x_i\le m$。数据有一定梯度。