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.

抽卡 【题目描述】

白浅妹妹最近在玩一个抽卡游戏，现在她决定进行 $n$ 连抽，每次抽出的角色有一个属性 $𝑎_𝑖$，如果相邻两次抽卡的角色属性的奇偶性不同，白浅妹妹的郁闷值就会增加 1，如果白浅妹妹太郁闷了，她就会跑到你旁边嘤嘤嘤。 为了不让白浅妹妹嘤嘤嘤，你努力拿到了接下来 $n$次的抽卡结果，然后你发现其中只有 $𝑚$ 次抽卡的结果是固定的，剩余$𝑛 −𝑚$ 次抽卡结果可指定。于是你可以调整这些可指定的抽卡结果的顺序使得白浅妹妹的郁闷值最小。

然而因为游戏公司做了神奇的保密操作，在接下来 $q$ 段时间里，某次结果可能由可指定变为固定，也有可能从固定变为可指定，你需要求出每段时间发生的变化后，白浅妹妹的最小郁闷值是多少。

sample.zip

【输入格式】

第一行包含三个整数 $𝑛$, $𝑚$, $𝑞$。 接下来一行 $n$ 个由空格分割的正整数 $𝑎_𝑖$，表示接下来所有$n$ 次的抽卡结果的集合。

接下来 $𝑚$ 行每行两个正整数 $𝑝_𝑖$ , $𝑏_𝑖$，表示第 $𝑝_𝑖$ 次的抽卡结果固定为 $𝑏_𝑖$。接下来 $q$ 行， 每行包含若干个整数，表示一种变化，具体如下：

• 变化 1：格式：$1𝑝$ 含义：第 $𝑝$ 次的抽卡结果变为不固定。
• 变化 2：格式：$2𝑝$ 含义：第 $𝑝$ 次的抽卡结果固定为 $𝑥$。 保证所有输入不会冲突。

【输出格式】

输出包含 $q$ 行，即为每次变化后白浅妹妹的最小郁闷值。

【样例 1 输入】

10 8 10
15 4 12 10 14 5 18 7 9 11
5 12
6 18
1 4
10 5
7 7
2 15
9 14
4 10
2 8 11
1 7
1 6
2 7 18
2 6 9
1 8
2 8 7
1 9
1 4
1 5

【样例 1 输出】

5
5
5
7
7
7
7
5
5
5

【备注】