题目描述

这个世界上总是有奇怪的抽卡游戏，现在小盖决定进行 $n$ 连抽，每次抽出的角色有一个阵营属性$a_i$,定义两个角色阵营属性$a_i,a_j$ 差别很大为$a_i,a_j$ 奇偶性不同。

如果相邻两次抽卡的角色阵营属性差别很大，小盖的郁闷值就会增加 1, 如果小盖太郁闷了，可能会导致他在大学物理考试中挂科。

为了不让小盖过于郁闷，你努力拿到了接下来 $n$ 次的抽卡结果，然后你发现其中只有 $m$ 次抽卡的结果是固定的，于是你可以调整剩下的抽卡结果的顺序使得小盖的郁闷值最小。

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

注意 ： $n$ 次抽卡操作会得到 $n$ 个数， 我们的 “固定” 操作的意思是在这 $n$ 个数中找到那个我们要 “固定” 的数放到对应的位置上去。对于“取消固定” 这个操作， 意思是取消对这个位置上的固定， 让这个位置上的数可以到任意地方去。

输入格式

第一行包含三个整数 $n,m,q$, 含义如题。

接下来一行 $n$ 个由空格分割的正整数 $a_i,$表示接下来所有$n$ 次的抽卡结果集

接下来 $m$ 行每行两个正整数 $p_i, b_i,$表示第$p_i$ 次的抽卡结果固定为 $b_i$。

接下来 $q$ 行，每行包含若干个整数，表示一种变化，具体如下：

• 变化 1: 格式：1 $p$ 含义：第 $p$ 次的抽卡结果变为不固定。
• 变化 2: 格式：2 $px$ 含义：第 $p$ 次的抽卡结果固定为 $x$。

输出格式

一共 $q$ 行, 每行一个整数表示最小郁闷值

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

5
5
5
7
7
7
7
5
5
5

此组样例满足subtask1。 
见sample2.in

见sample2.ans

此组样例满足subtask2。 
见sample3.in

见sample3.ans

此组样例满足subtask4。 
见sample4.in

见sample4.ans

此组样例满足subtask 5。 
见sample5.in

见sample5.ans

例如 ：对于样例一，在第一次操作之前， 我们的集合是 $\{9, 11\}$，其余位置是 $(4,15, -1 ,10, 12, 18, 7, -1 ,14 ,5)$ ,其中 $-1$ 表示这个位置没有填数， 接下来一次操作固定 $11$ 到位置 $8$， 序列变成 $(4,15, -1 ,10, 12, 18, 7, 11 ,14 ,5)$， 此时答案是 $5$ 。

数据规模与约定

$subtask1(15pts)\:n\leq20,q\leq5$

$subtask2(15pts)\:n\leq100,q\leq100$

$subtask3(20pts)\:n\leq5000,q\leq5000$

$subtask4(30pts)\:n\leq10^4,q\leq10^4,\:$ 任意时刻可随意指定的阵营属性为奇数的角色不超过 4 个，且该点时限 1.5s。

$subtask5(20pts)\:n\leq10^6,q\leq10^6$ 保证变化过程中数据一定合法。保证所有输入整数在 int 范围以内。

大样例

大样例下载