Public Judge

pjudge

Time Limit: 2 s Memory Limit: 256 MB Total points: 100 Hackable ✓
[+7]

# 21705. 【NOIP Round #4】序列

Statistics

题目描述

今天是 YQH 的生日,她得到了一个长度为 n 的整数序列 a1,a2,,an 作为生日礼物。

然而,YQH 并不对这个序列满意,因为这个序列可能并不合法。

一个序列 {ai} 合法,当且仅当 nmaxi=1{ai}+nmini=1{ai}>n,其中 n 为序列长度,特别的,我们规定 是合法的。

为了让 YQH 满意,你需要找到一个 a1,a2,,an 的一个子段,使得这个子段是合法的。一个序列 b1,b2,,bma1,a2,,an 的子段当且仅当 b1,b2,,bm 可以由 a1,a2,,an 删掉若干个(可以为 0)开头及结尾的元素得到,比如 [2,3],[1,2],[3,4],[1,2,3,4], 都是 [1,2,3,4] 的子段。

符合条件的子段可能很多,所以 YQH 只想要你找到,a1,a2,,an 的所有合法子段的长度的最大值。

然而,YQH 得到的序列有魔力,所以它会产生变化,YQH 希望你对于初始的以及每次变化后的 {ai} 都求出答案。

输入格式

第一行一个正整数及一个非负整数 n,m。其中 m{ai} 的变化次数。

第二行 n 个整数表示初始的 a1,a2,,an

接下来,描述 m 次变化,每次变化由若干行描述:

其中第一行一个非负整数表示 k,接下来 k 行,第 i 行两个正整数 xi,yi。假如变化前的序列为 {ai},那么对 {ai} 依次交换 (ax1,ay1),(ax2,ay2),,(axk,ayk),得到的序列 {ai} 就是变化后的序列。

变化之间不独立(见样例解释)

输出格式

第一行一个整数表示初始 {ai} 的答案。

接下来 m 行,第 i 行一个整数表示第 i 次变化后的答案。

样例

输入1

5 2
1 2 -2 3 4
1
2 3
1
1 2

输出1

2
3
4

{ai} 初始为 [1,2,2,3,4],其中一个合法子段为 [3,4]

第一次变化,交换 (a2,a3){ai}[1,2,2,3,4],其中一个合法子段为 [2,3,4]

第二次变化,交换 (a1,a2){ai}[2,1,2,3,4],其中一个合法子段为 [1,2,3,4]

输入2

5 2
-1 -1 2 1 1
2
3 4
2 5
2
2 5
1 4

输出2

2
2
1

{ai} 初始为 [1,1,2,1,1],其中一个合法子段为 [2,1]

第一次变化,先交换 (a3,a4),再交换 (a2,a5),最终 {ai}[1,1,1,2,1],其中一个合法子段为 [1,2]

第二次变化,先交换 (a2,a5),再交换 (a1,a4),最终 {ai}[2,1,1,1,1],其中一个合法子段为 [1]

样例输入/输出 3

见下发文件中的 ex_loose3.in/ex_loose3.ans

样例输入/输出 4

见下发文件中的 ex_loose4.in/ex_loose4.ans

数据范围

令所有变化的交换次数 k 之和为 K

对于所有数据,保证 1n106,0m30,0K106,|ai|109,xiyi

子任务编号 n m 分值
1 2000 30 20
2 2×105 2 20
3 106 2 20
4 106 30 40